@ysner
2018-07-18T23:51:25.000000Z
字数 1168
阅读 2414
贪心
你如此计算一个正整数的荒谬程度:
询问在范围内荒谬度最低的数。()
一开始想的是,初始,从低位往高位处理,先看该位能否加到(同时前一位加);再看能否加到。
但这样疏漏很多,而且不好针对性,如比优先级高。
而思路妙多了,从开始,每次最后一个非零数位加一并统计答案,这样完全没有漏情况可能。
复杂度上限???
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
int ans=0,mn,now;
il ll gi()
{
re ll x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il int add(re int x)
{
re int res=1;
while(x%10==0) x/=10,res*=10;
return res;
}
il int calc(re int x)
{
while(x%10==0) x/=10;
re int tot=0,las=x%10;
while(x) x/=10,tot++;
return 2*tot-(las==5);
}
int main()
{
re int T=gi();
while(T--)
{
re int l=gi(),r=gi();
mn=calc(l),now=ans=l;
while(1)
{
now+=add(now);
if(now>r) break;
re int t=calc(now);
if(t<mn) mn=t,ans=now;
}
printf("%d\n",ans);
}
return 0;
}