算法1
你可以看出来第二个算法和第一个算法为什么要再写一个比较函数,而不直接利用字典序进行比较吗~
C++ 代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1E5 + 8;
ll n, k, a[N];
string s[N], ss;
int orz(string s, string ss){
if(s.size() == ss.size()){
if(s < ss) return 1;
if(s == ss) return 0;
if(s > ss) return -1;
}
if(s.size() < ss.size()) return 1;
return -1;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
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]);
ss = to_string(k);
ll res = 0;
int l = 1, r = n;
while(l <= r){
int omg = orz(s[l] + s[r], ss);
if(omg == 1){
res += r - l;
++ l;
}
else if(!omg){
res += r - l;
++ l, -- r;
}
else -- r;
}
l = 1, r = n;
while(l <= r){
int omg = orz(s[r] + s[l], ss);
if(omg == 1){
res += r - l;
++ l;
}
else if(!omg){
res += r - l;
-- r, ++ l;
}
else -- r;
}
cout << res;
return 0;
}
算法2
C++ 代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1E5 + 8;
int n, k, a[N];
string s[N], ss;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
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]);
ss = to_string(k);
ll res = 0;
int l = 1, r = n;
while(l <= r){
if(s[l] + s[r] < ss){
res += r - l;
++ l;
}
else if(s[l] + s[r] == ss){
res += r - l;
++ l, -- r;
}
else -- r;
}
l = 1, r = n;
while(l <= r){
if(s[r] + s[l] < ss){
res += r - l;
++ l;
}
else if(s[r] + s[l] == ss){
res += r - l;
-- r, ++ l;
}
else -- r;
}
cout << res;
return 0;
}