题目链接：点击打开链接φ(>ω<*)
要使每个月的钱都大于常数C，就要使每次花的冤枉钱最少
1，输入时便不记录那些大于C的面额，直接加
cin>>N>>C; for(int i=0,lin=0;i<N;i++){ int l1,l2; cin>>l1>>l2; if(l1>=C)sum+=l2; else{s[lin].a=l1,s[lin].b=l2;lin++;} }
2,剩下的记录在数组s中的便全是小于C的面额；
利用sort函数按面值从小到大排列
整个过程在while(1)中进行
从大的开始找，在s[i].b>0&&x>=s[i].a的情况下x-=s[i].a;
如C=13，s[i].a=4，就减三次，剩下1；
如果 s[i].a=10，就减两次，无剩余
int x=C; for(i=lin-1;i>=0;i--){ if(s[i].b>0&&x>=s[i].a){ for(;s[i].b>0&&x>=s[i].a;){ x-=s[i].a; s[i].b--; } } }
3，如果x>0(还有剩余)
从小的里面挑大于x的去减；
if(x>0)for(i=0;i<lin;i++){ if(s[i].b>0&&x<=s[i].a){ x-=s[i].a; s[i].b--; break; } }
4，最后sum++，如果x还大于0正面已经无法满足，结束循环
sum++; if(x>0)break;
完成代码如下：
#include<iostream> #include<cstring> #include<cstdlib> using namespace std; const int M=10000000; struct lin{ int a; int b; }s[30]; int cmp(const void*x,const void*y){ struct lin*x1=(lin*)x; struct lin*x2=(lin*)y; return x1->a-x2->a; } int main(){ int i,N,C,lin=0,sum=0; cin>>N>>C; for(i=0;i<N;i++){ int l1,l2; cin>>l1>>l2; if(l1>=C)sum+=l2; else{s[lin].a=l1,s[lin].b=l2;lin++;} } qsort(s,lin,sizeof(s[0]),cmp); while(1){ int x=C; for(i=lin-1;i>=0;i--){ if(s[i].b>0&&x>=s[i].a){ for(;s[i].b>0&&x>=s[i].a;){ x-=s[i].a; s[i].b--; } } } if(x>0)for(i=0;i<lin;i++){ if(s[i].b>0&&x<=s[i].a){ x-=s[i].a; s[i].b--; break; } } if(x>0)break; sum++; } cout<<sum; return 0; }
φ(>ω<*) (〃'▽'〃)(｀・ω・´)
