思路:
排序加上二分,首先排序,预处理每一个数提升数位之后的值(注意此时数据范围有可能超过long long),然后遍历每一数,用k减去这个数,然后利用二分寻找小于差值的数量,注意可能包含自身,需要减一。
代码:
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
long long n,k;
long long sum=0;
int num[100010];
unsigned long long num1[11][100010];
int smaller_num(int p,int x,long long target){
int l=0,r=n-1,mid;
if(num1[x][0]>target) return 0;
while(l<r)
{
mid=l+r+1>>1;
if(num1[x][mid]<=target) l=mid;
else r=mid-1;
}
return l>=p?l:l+1;
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++) scanf("%d",&num[i]);
sort(num,num+n);
for(int i=0;i<n;i++)
{
for(long long j=1,t=num[i];j<11;j++)
{
num1[j][i]=t*10;
t*=10;
}
}
for(int i=0;i<n;i++)
{
sum+=point(i,to_string(num[i]).size(),k-num[i]);
}
cout<<sum;
return 0;
}