BZOJ 4029 HEOI2015 定价数位贪心

发布时间：2020-12-13 20:10:00 所属栏目：PHP教程来源：网络整理

导读：题目大意：定义1个数的荒诞程度为去掉末尾所有 0 后的数字数量 ? 2 (若末尾为 5 则荒诞程度减掉 1 )，求 [ l , r ] 区间内荒诞程度最小的数字(若多个相同取最小) 从高位往低位贪心便可。注意500的荒诞程度比100低 #include assert.h #include cstdio #inclu

题目大意：定义1个数的荒诞程度为去掉末尾所有 $0$ 后的数字数量 $*2$ (若末尾为 $5$ 则荒诞程度减掉 $1$ )，求 $[l,r]$ 区间内荒诞程度最小的数字(若多个相同取最小)
从高位往低位贪心便可。
注意500的荒诞程度比100低

#include <assert.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int Calculate(long long l,long long r)
{
    long long temp,ans=0;
    for(temp=1;temp<=l;temp*=10);
    if(temp/2>=l&&temp/2<=r)
        return temp/2;
    if(temp*5<=r)
        return temp*5;
    temp/=10;
    for(;temp;temp/=10)
    {
        long long target;

        target=l-l%temp+(bool)(l%temp)*temp; 
        if( r>=target )
            return ans+target;

        if(l%temp<=temp/2)
        {
            target=l-l%temp+temp/2;
            if(r>=target)
                return ans+target;
        }
        ans+=l-l%temp;
        l%=temp;r%=temp;
    }
    assert(false);
}
int main()
{
    //freopen("4029.in","r",stdin);
    //freopen("4029.out","w",stdout);
    int T,l,r;
    for(cin>>T;T;T--)
    {
        scanf("%d%d",&l,&r);
        printf("%d
",Calculate(l,r));
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

BZOJ 4029 HEOI2015 定价 数位贪心

BZOJ 4029 HEOI2015 定价数位贪心