题解 P4109 【[HEOI2015]定价】

_Lemon_ · 2018-07-17 11:54:29 · 题解

根据题意，很容易可以想到价格后面尽可能多0,在此基础上需要尽量最后一个数字是5。 那么我们可以想到每次更新的时候尽量跳10^N(就算是10，10^9/10=10^8也大概可以卡过)并且因为需要输出最小的，所以要从小开始找 PS：判断ANS=1会很快。

#include<bits/stdc++.h>
using namespace std;
long long deal(long long k)
{
    int len=0;
    while(k>0)
    {
        k/=10;
        len++;
    }
    long long Lemon=1;
    for(int i=1;i<len;i++)
        Lemon*=10;
    return Lemon;
}
int get(long long k)
{
    int Lemon=0,answer=0;
    while(k%10==0) k/=10;
    if(k%10==5) Lemon=1;
    while(k>0)
    {
        k/=10;
        answer++;
    }
    return answer*2-Lemon;
}
void solve()
{
    int ans=1000005;
    long long l,L,R,cha,ansnum;
    scanf("%lld%lld",&L,&R);
    cha=R-L;
    cha=min(cha,L);
    long long Lemon=deal(cha);
    l=L-(L%Lemon);
    while(1)
    {
        if(l>=L) 
            if(ans>get(l)) 
                {
                    ans=get(l);
                    ansnum=l;
                }
        l+=Lemon;
        if(l>R) break ;
        if(ans==1) break ;//记得特判一
    }
    printf("%lld\n",ansnum);
    return ;
}
int main()
{
    int T;
    cin>>T;
    for(int cao=1;cao<=T;cao++)
        solve();
    return 0;
}