欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【hdu5527】【2015ACM/ICPC亚洲区长春站 】Too Rich

程序员文章站 2022-05-09 20:39:15
题意&题解: 感觉自己真是弱啊,自己想的贪心是错的,根本没想到20,50的特判,╮(╯▽╰)╭ 代码: (几乎和那位聚聚的一样,ORZ) #include #in...


题意&题解:
感觉自己真是弱啊,自己想的贪心是错的,根本没想到20,50的特判,╮(╯▽╰)╭
代码:
(几乎和那位聚聚的一样,ORZ)

#include
#include
#include
#include
using namespace std;
int val[11]={0,1,5,10,20,50,100,200,500,1000,2000};
int x,T,p,num[11],vis[11],use[11];
int ans=-1;
long long sum;
int solve()
{
    memset(use,0,sizeof(use));
    if (vis[5]>num[5] || vis[8]>num[8]) return 0;
    long long tmp=vis[5]*val[5]+vis[8]*val[8];
    int tmpn=vis[5]+vis[8];
    for (int i=1;i<=10;i++)
    {
        if (vis[i]==-1)
        {
            tmp+=num[i]*val[i];
            tmpn+=num[i];
            use[i]=num[i];
        }
        else
        {
            use[i]=num[i]-vis[i];
            if (use[i]%2==1) use[i]--;
            tmpn+=use[i];
            tmp+=use[i]*val[i];
        }
        if (tmp>=x)
        {
            long long chao=tmp-x;
            for (int j=i;j>=1;j--)
            {
                if (vis[j]==-1)
                {
                    long long tui=min((long long)use[j],chao/val[j]);
                    tmpn-=tui;
                    chao-=tui*val[j];               
                }
                else
                {
                    long long tui=min((long long)use[j],chao/val[j]);
                    if (tui%2==1) tui--;                    
                    tmpn-=tui;
                    chao-=tui*val[j];
                }
                if (chao==0)
                {
                    ans=max(ans,tmpn);
                    return 0;
                }
            }
            return 0;
        }
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&x);
        memset(vis,-1,sizeof(vis));     
        for (int i=1;i<=10;i++)
        {
            scanf("%d",&num[i]);
            sum+=num[i]*val[i];
        }
        if (sum