算法1
(双指针) $O(nlogn)$
从数组里面选取两个数字,进行拼接,暴力枚举时间复杂度为$O(n^2)$,会超时。
使用双指针算法,先将数组进行排序,左指针指向数组开始点,右指针指向数组结束点,向中间移动。
对于两个指针选取到的数,我们进行拼接。
如果拼接后的数字小于k,那么由于r指针指向的是目前的最大值,l~r之间的所有数字和l拼接起来都小于k,所以res+=r-l,并且更新左指针l++;
如果拼接后的数字等于k,同理res+=r-l,但是此时需要同时更新l,r指针,l++,r–;
如果拼接后的数字大于k,不更新答案,r–即可
由于拼接操作两个数字分别放前面,后面算两种方案,所以我们进行两遍双指针,分别跑放前面、放后面即可。
对于拼接操作,如果直接使用数字进行拼接比较麻烦,可以转化为字符串再进行拼接,但需要自己手写一个比较大小的函数
C++ 代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll a[N];
string s[N], sk;
ll n, k;
ll res;
int cmp(string s1, string s2) { // 字符串大小比较函数
if(s1.size() == s2.size()) {
if(s1 == s2) return 0;
else if(s1 < s2) return 1;
else return -1;
}
if(s1.size() < s2.size()) return 1;
else return -1;
}
int main() {
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n; i++) s[i] = to_string(a[i]);
sk = to_string(k);
int l = 1, r = n;
while(l <= r) { // l放前面r放后面拼接
int t = cmp(s[l] + s[r], sk);
if(t == 1) { // 拼接后小于k
res += r - l;
l++;
} else if(t == 0) { // 拼接后等于k
res += r - l;
l++, r--;
} else r--; // 拼接后大于k
}
l = 1, r = n;
while(l <= r) { // r放前面l放后面拼接
int t = cmp(s[r] + s[l], sk);
if(t == 1) {
res += r - l;
l++;
} else if(t == 0) {
res += r - l;
l++, r--;
} else r--;
}
cout << res;
return 0;
}
直接字符串的比较为什么不可以,不能按字典序排吗?
我知道了,可能会出现39>333的情况…
强
orz