BZOJ1685: [Usaco2005 Oct]Allowance 津贴

【传送门：BZOJ1685】

简要题意：

　　贝西工作勤勤恳恳，她每月向约翰索要C 元钱作为工资。约翰手上有不少钱，他一共有N 种面额的钞票。第i 种钞票的面额记作Vi，约翰有Ki 张。钞票的面额设定是比较合理的，保证所有大面额的钞票都是所有小面额钞票的整数倍。假设约翰每个月给贝西发一次工资，那么这些钱够发几个月的工资呢？贝西不会找零，如果约翰发的钱大于C 元，多余的部分就算是贝西的奖励了。

输入格式：

　　• 第一行：两个整数N 和C，1 ≤ N ≤ 20, 1 ≤ C ≤ 10^9

　　• 第二行到第N + 1 行：第i + 1 行有两个整数Vi 和Ki，1 ≤ Vi ≤ 10^9; 1 ≤ Ki ≤ 10^6

输出格式：

　　• 单个整数：表示约翰最多能给贝西发几个月的工资

样例输入：

3 6

10 1

1 100

5 120

样例输出：

111

样例解释：

　　第一个月先给一张十元的，接下来十个月每个月都给两张五元的，最后一百个月每月给一张一元的和一张五元的

题解：

　　贪心，主要思路就是不停得一个月一个月操作，先选大面额的再选小面额的，然后无法刚好达到C元，就选一个当前最小的面额来补充（即使已经超出C元）

参考代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cmath>

using namespace std;

struct node

{

    int v,c;

}a[];

int cmp(const void *xx,const void *yy)

{

    node n1=*(node *)xx;

    node n2=*(node *)yy;

    if(n1.v>n2.v) return -;

    if(n1.v<n2.v) return ;

    return ;

}

int main()

{

    int n,c;

    scanf("%d%d",&n,&c);

    for(int i=;i<=n;i++) scanf("%d%d",&a[i].v,&a[i].c);

    qsort(a+,n,sizeof(node),cmp);

    int ans=;

    while()

    {

        int cc=c;

        bool bk=false;

        for(int i=;i<=n;i++)

        {

            if(a[i].c==) continue;

            if(cc<=)

            {

                bk=true;

                break;

            }

            int d=cc/a[i].v;

            if(d>a[i].c)

            {

                cc-=a[i].v*a[i].c;

                a[i].c=;

            }

            else

            {

                cc-=a[i].v*d;

                a[i].c-=d;

            }

        }

        if(cc>)

        {

            for(int i=n;i>=;i--)

            {

                if(a[i].c!=)

                {

                    a[i].c--;

                    bk=true;break;

                }

            }

        }

        if(bk==true||cc<=) ans++;

        else break;

    }

    printf("%d\n",ans);

    return ;

}

巴特西