按价格排序后贪心
——代码
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 }