您当前位置：首页 > php开源 > php教程 > BZOJ 4029 HEOI2015 定价数位贪心

BZOJ 4029 HEOI2015 定价数位贪心

来源：程序员人生发布时间：2015-05-15 08:30:09 阅读次数：2812次

题目大意：定义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;
}

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 mac pro安装双系统及简单开发环境搭建

下一篇 干货分享，图片模糊算法，解析xml绘制图片

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点

BZOJ 4029 HEOI2015 定价 数位贪心

BZOJ 4029 HEOI2015 定价数位贪心