P1032 （C++代码）

解题思路:





注意事项:





参考代码:洗脑开始：

要使每个月的钱都大于常数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;
完成代码如下：
[cpp] view plain copy
#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;  
}