题意:中文你懂得
其实我们仔细想想如果同样位数,那么0结尾的必定最好,其次是5,再者是尾数最小的那个数。这样我们从一个数的最后一位开始模拟进位计算,使得这个数在上限之内的最小p就好,其实我算法还可以优化一下,40ms比较慢了。
题目地址:http://www.lydsy.com/JudgeOnline/problem.php?id=4029
代码:
Memory: 1300 KB | Time: 40 MS | |
Language: C++ | Result: Accepted |
#include <iostream> #include <cmath> using namespace std; struct One{int len, e;}; One get_one(int x){ int len=0; One one; while(x%10==0)x/=10; one.e=x%10; while(x){ len++; x/=10; } one.len=len; return one; } int intlen(int x){ int len=0; while(x){ len++; x/=10; } return len; } int main() { int t, l, r, p, tans, ans; cin>>t; while(t--){ cin>>l>>r; tans = ans = l; One one = get_one(l); p=2*one.len; if(one.e==5)p-=1; //贪心0和5 int tlen, tp, jc=0; while(tans<=r){ tans+=pow(10, jc); if(tans>r)break; one = get_one(tans); tp = 2*one.len; if(one.e==5)tp-=1; if(tp<p){p=tp;ans=tans;} jc = intlen(tans)-one.len; } cout<<ans<<endl; } return 0; }