题意

1 给出n种面值的货币, 并给出数量, 每次去除C元钱, 问最短能取多少回

分析

1 面值比c大的直接当一次

2 面值比C小的贪心求解, 具体分析在注释里

参考代码

struct T{ int value,num; bool operator<(const T&a) {     return value< a.value; }};T ar[23];int need[20+6];int main(void){   int N,C;   while(cin>>N>>C)   {       int sum = 0;       int number = 0;      fo1(i,N)      {          int a,b;          cin>>a>>b;          if(a>=C)//大于C的情况            sum+=b;          else          {              ar[number].value = a;              ar[number++].num = b;          }      }     sort(ar,ar+number);//按面值大小排序//     cout<
     
      <
      
       =0;--i)//从大面值到小面值遍历,使得总和小于等于C         {            if(ar[i].num)//如果还有剩余            {                need[i] = min(ar[i].num,tmp/ar[i].value);//最多能用第i中面值的货币多少被                tmp -= need[i]*ar[i].value;            }//            if(tmp==0)//                break;         }         for(int i = 0;i < number; ++i)//从小到到大遍历,使得总和大于等于C         {             int d = min(ar[i].num-need[i],(tmp+ar[i].value-1)/ar[i].value);//这个是重点, 使得总和大于C<=sum
       
        0)//如果剩下的钱不够C            break;         else         {             int t = INF;//t代表这种组合最多能取多少次             for(int i = 0;i < number; ++i)              {                  if(need[i])                    t = min(t,ar[i].num/need[i]);              }             for(int i = 0;i