1 条题解
-
1
从数组里面选取两个数字,进行拼接,暴力枚举时间复杂度为 ,会超时。 我们可以使用双指针算法,先将数组进行排序,左指针指向数组开始点,右指针指向数组结束点,向中间移动。对于两个指针选取到的数,进行拼接。 如果拼接后的数字小于 k,那么因为 指针指向的是目前的最大值,所以 区间内的所有数字与 拼接的结果都小于 ,所以答案加上 ,并且更新左指针;
如果拼接后的数字等于 k,同理答案加上 r - l,但是此时需要同时更新左、右指针 , ;
如果拼接后的数字大于 k,不更新答案,更新右指针 即可。
由于交换 a[i]和a[j]的顺序总是被视为 2 种拼法,所以我们跑两遍双指针,分别放前面、放后面即可。
参考代码
#include<bits/stdc++.h> using namespace std; int n, ans; long long k, a[100010]; long long pj(int i, int j) //整数i与整数j拼接 { long long tj = j, sj = 1; while (tj > 0) { sj *= 10; //算出整数j的位数 tj /= 10; } return i * sj + j; } int main() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); //将数组从小到大排列 int i = 1, j = n; while (i != j) { long long t = pj(a[i], a[j]); if (t <= k) { ans += j - i; //如果小于等于k,那么统计答案 i++; } else j--; //否则移动j指针,缩小范围 } //反着再拼一遍 i = 1; j = n; while (i != j) { long long t = pj(a[j], a[i]); if (t <= k) { ans += j - i; i++; } else j--; } cout << ans; return 0; }
- 1
信息
- ID
- 690
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- (无)
- 递交数
- 54
- 已通过
- 37
- 上传者