题意:中文你懂得

其实我们仔细想想如果同样位数,那么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;
}