[luoguP2983] [USACO10FEB]购买巧克力Chocolate Buying（贪心）

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 
 5 int n;
 6 long long m, ans;
 7 struct node
 8 {
 9     long long x, y;
10 }p[100001];
11 
12 inline long long read()
13 {
14     long long x = 0, f = 1;
15     char ch = getchar();
16     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
17     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
18     return x * f;
19 }
20 
21 inline bool cmp(node x, node y)
22 {
23     return x.x < y.x;
24 }
25 
26 int main()
27 {
28     int i;
29     long long k;
30     n = read();
31     m = read();
32     for(i = 1; i <= n; i++) p[i].x = read(), p[i].y = read();
33     std::sort(p + 1, p + n + 1, cmp);
34     for(i = 1; i <= n; i++)
35     {
36         k = m / p[i].x;
37         if(k > p[i].y)
38         {
39             m -= p[i].x * p[i].y;
40             ans += p[i].y;
41         }
42         else
43         {
44             ans += k;
45             break;
46         }
47     }
48     printf("%lld
", ans);
49     return 0;
50 }