洛谷 P2376 [USACO09OCT]津贴Allowance

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<vector>
 5 using namespace std;
 6 #define fi first
 7 #define se second
 8 #define mp make_pair
 9 #define pb push_back
10 typedef long long ll;
11 typedef unsigned long long ull;
12 typedef pair<int,int> pii;
13 int n,c;
14 int ans;
15 pii t1[1010];
16 int len;
17 int main()
18 {
19     int t,i,x,y,s;
20     bool fl;
21     scanf("%d%d",&n,&c);
22     for(i=1;i<=n;i++)
23     {
24         scanf("%d%d",&x,&y);
25         if(x>=c)    ans+=y;
26         else    t1[++len]=mp(x,y);
27     }
28     sort(t1+1,t1+len+1);
29     while(1)
30     {
31         fl=0;
32         for(i=1;i<=len;i++)
33             if(t1[i].se!=0)
34                 fl=1;
35         if(!fl)    break;
36         s=0;
37         for(i=len;i>=1;i--)
38         {
39             t=min(t1[i].se,(c-s)/t1[i].fi);
40             s+=t1[i].fi*t;
41             t1[i].se-=t;
42         }
43         if(s<c)
44         {
45             fl=0;
46             for(i=1;i<=len;i++)
47                 if(t1[i].se!=0)
48                     fl=1;
49             if(!fl)    break;
50             for(i=1;i<=len;i++)
51                 if(t1[i].se)
52                 {
53                     --t1[i].se;
54                     break;
55                 }
56         }
57         ans++;
58     }
59     printf("%d",ans);
60     return 0;
61 }