【传送门：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[21]; int cmp(const void *xx,const void *yy) { node n1=*(node *)xx; node n2=*(node *)yy; if(n1.v>n2.v) return -1; if(n1.v<n2.v) return 1; return 0; } int main() { int n,c; scanf("%d%d",&n,&c); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].v,&a[i].c); qsort(a+1,n,sizeof(node),cmp); int ans=0; while(1) { int cc=c; bool bk=false; for(int i=1;i<=n;i++) { if(a[i].c==0) continue; if(cc<=0) { bk=true; break; } int d=cc/a[i].v; if(d>a[i].c) { cc-=a[i].v*a[i].c; a[i].c=0; } else { cc-=a[i].v*d; a[i].c-=d; } } if(cc>0) { for(int i=n;i>=1;i--) { if(a[i].c!=0) { a[i].c--; bk=true;break; } } } if(bk==true||cc<=0) ans++; else break; } printf("%d ",ans); return 0; }