终于自主写出了一道题,太难了,虽然很简单但是这是算法生涯的一大步!
这一题有100个测试数据,而且n的数字高达10^9所以很明显不能枚举,所以要进行预处理,很容易发现其实没有那么多的幸运年,所以先将所有的幸运年都处理出来,然后用二分出第一个大于等于当前年份的年份,当不同时再加一即可。
题目描述
如果一个年份的各位数字中非零数字不超过 1 个,则称该年是一个幸运年。
比如,100,40000,5 都是幸运年,而 12,3001,12345 则不是幸运年。
现在,给定你一个年份,请你求出当前年份距离下一个幸运年多少年?
第一行包含整数 T,表示共有 T 组测试数据。
每组数据包含一个整数 n,表示当前年份。
输出格式
每组数据输出一行,一个整数,表示距离下一个幸运年的年数。
数据范围
1≤T≤100,
1≤n≤109。
样例
输入样例1:
3
4
201
4000
输出样例1:
1
99
1000
算法
(预处理+二分)
时间复杂度
$O(t*logm)$
C++ 代码
#include<iostream>
using namespace std;
long long a[200];
int sum;
int cn(int i){
int res=1;
for(int j=1;j<=i;j++)
res*=10;
return res;
}
int main(){
for(int i=0;i<=8;i++)
for(int j=1;j<=9;j++)
a[++sum]=j*cn(i);
a[++sum]=1000000000;
a[++sum]=2000000000;
int n;
cin>>n;
while(n--){
int m;
cin>>m;
int l=1,r=sum;
while(l<r){
int mid=l+r>>1;
if(m<=a[mid])r=mid;
else l=mid+1;
}
if(a[l]!=m)cout<<a[l]-m<<endl;
else cout<<a[l+1]-m<<endl;
}
}
nice
谢谢