4月13日

poj3040

题意:给定一堆纸笔，及每种纸币的面额和张数，每周发的钱不能少于t，问这些纸币最多可以发几周

分析:非常好的贪心题目，思路很简单，先用面额大的来发，不够再用小的来进行填补，但是实现起来并不是特别容易

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <vector>
 6 #include <algorithm>
 7 #include <set>
 8 #include <map>
 9 #include <bitset>
10 #include <cmath>
11 #include <queue>
12 #include <stack>
13 using namespace std;
14 const int maxn=25;
15 typedef struct p
16 {
17     int value,num;
18 }p;
19 bool cmp(p a,p b)
20 {
21     return a.value>b.value;
22 }
23 p s[maxn];
24 int n,t;
25 int need[maxn];
26 int main()
27 {
28     while(cin>>n>>t)
29     {
30         int mx;
31         for(int i=0;i<n;i++)
32             cin>>s[i].value>>s[i].num;
33         sort(s,s+n,cmp);
34         int cnt=0;
35         for(int i=0;i<n;i++) //比t大的直接加上即可
36         {
37             if(s[i].value>=t)
38             {
39                 cnt+=s[i].num;
40                 s[i].num=0;
41             }
42         }
43         while(true)
44         {
45             int sum=t,flag=0;
46             memset(need,0,sizeof(need));
47             for(int i=0;i<n;i++) //从大到小进行分配看剩余多少
48             {
49                 int tmp=sum/s[i].value;
50                 int mi=min(tmp,s[i].num);
51                 sum-=mi*s[i].value;
52                 need[i]=mi;
53                 if(sum<=0){
54                     flag=1; break;
55                 }
56             }
57             if(sum>0)
58             {
59                 for(int i=n-1;i>=0;i--) //从小到大进行填充
60                 {
61                     if(need[i]<s[i].num)
62                     {
63                         while(need[i]<s[i].num)
64                         {
65                             sum-=s[i].value;
66                             need[i]++;
67                             if(sum<=0){
68                                 flag=1; break;
69                             }
70                         }
71                     }
72                     if(flag)  break;
73                 }
74             }
75             if(!flag)  break;
76             mx=0x3ffff;
77             for(int i=n-1;i>=0;i--) //统计这样的分配方式最多有几种
78             {
79                 if(need[i])
80                     mx=min(mx,s[i].num/need[i]);
81             }
82             cnt+=mx;
83             for(int i=n-1;i>=0;i--)
84             {
85                 if(need[i])
86                     s[i].num-=mx*need[i];
87             }
88         }
89         cout<<cnt<<endl;
90     }
91     return 0;
92 }

View Code