小花爱吃鱼，这是全世界都知道的事情。它的好朋友编程兔给它准备了很多的零食，每一样都是小花喜欢的。当然了，里面最多的肯定是鱼。某一天编程兔给小花准备了两种鱼，一种鱼的重量是1，另一种鱼的重量是2，重量为1的鱼有不同的美味值，重量为2的鱼也有不同的美味值。现在假设小花的胃口最多能吃下不超过重量为v的鱼，小花希望吃掉的鱼的美味值总和最大。
第一行是两个正整数n和v，n表示鱼的数量，v表示小花的胃口。
接下来n行，每行两个正整数，第一个正整数表示鱼的重量（只有1和2两种可能），另一个正整数表示这条的美味值。
一行，一个整数，表示小花能得到的最大美味值总和。
3 2
1 2
2 7
1 3
7
小花选择了第2条鱼吃，美味值是7。
对于60%的数据，1≤n≤2000。
对于100%的数据，1≤n≤30000，1≤v≤60000，每条鱼的美味值不超过10000。
这道题其实是一道暴力枚举题，但是有一种贪心做法还是可取的。
下面把重量为1的鱼称为鱼1，重量为2的鱼称为鱼2.
首先尽可能吃价值高的鱼1，吃完还没饱再尽可能吃价值高的鱼2.
此时尝试用剩下的鱼2去换鱼1，取最优即可。
最后要判断是否还有剩余空间。
#include <iostream> #include <cstdio> #include <algorithm> #define MAX_N 30000 #define MAX_M 60000 using namespace std; int n; int m; struct Fish { int w; int v; inline bool operator < (const Fish & x) const { if(w != x.w) return w < x.w; return v > x.v; } }; Fish a[MAX_N + 5]; int ans; int main() { scanf("%d%d", &n, &m); int mid = 0; for(register int i = 1; i <= n; ++i) { scanf("%d%d", &a[i].w, &a[i].v); if(a[i].w & 1) ++mid; } sort(a + 1, a + n + 1); int i = 0, j = mid; while(i < mid && i < m) { ans += a[++i].v; } while(j < n && i + (j - mid + 1 << 1) <= m) { ans += a[++j].v; } while(i >= 2 && j < n && a[i].v + a[i - 1].v <= a[j + 1].v) { ans += a[++j].v - a[i--].v - a[i--].v; } if(i < mid && i + (j - mid << 1) < m) { ans += a[++i].v; } printf("%d", ans); return 0; }
下面也附上暴力程序。只需要运用前缀和
#include <iostream> #include <cstdio> #include <algorithm> #define MAX_N 30000 #define MAX_M 60000 using namespace std; int n; int m; struct Fish { int w; int v; inline bool operator < (const Fish & x) const { if(w != x.w) return w < x.w; return v > x.v; } }; Fish a[MAX_N + 5], b[MAX_N + 5]; int ans; int main() { scanf("%d%d", &n, &m); int mid = 0; for(register int i = 1; i <= n; ++i) { scanf("%d%d", &a[i].w, &a[i].v); if(a[i].w & 1) ++mid; } sort(a + 1, a + n + 1); int i = 0, j = mid; while(i < mid && i < m) { ans += a[++i].v; } while(j < n && i + (j - mid + 1 << 1) <= m) { ans += a[++j].v; } while(i >= 2 && j < n && a[i].v + a[i - 1].v <= a[j + 1].v) { ans += a[++j].v - a[i--].v - a[i--].v; } if(i < mid && i + (j - mid << 1) < m) { ans += a[++i].v; } printf("%d", ans); return 0; }
原文：https://www.cnblogs.com/kcn999/p/10456142.html
