为什么我会用二分
思路
我们可以先将金币喷泉和钻石喷泉分离出来,进行分类讨论。
#include <cstdio> #include <algorithm> using namespace std; const int MAXN = 1e5 + 5; int n, c, d, ans, res; struct Node { int val, cost; bool operator < (const Node o) { return cost < o.cost; } } a[MAXN], b[MAXN]; int pre[MAXN]; int tot1, tot2; int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while ('0' <= ch && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); } return x * f; } int main() { scanf("%d %d %d", &n, &c, &d); for (int i = 1; i <= n; i++) { int val, cost; char ch; scanf("%d %d %c", &val, &cost, &ch); if (ch == 'C' && cost <= c) a[++tot1].val = val, a[tot1].cost = cost; else if (ch == 'D' && cost <= d) b[++tot2].val = val, b[tot2].cost = cost; } sort(a + 1, a + tot1 + 1); sort(b + 1, b + tot2 + 1); int res1 = 0, res2 = 0; int flag = 0; for (int i = 1; i <= tot1; i++) if (a[i].cost <= c) { res1 = max(res1, a[i].val); if (!flag) flag++; } for (int i = 1; i <= tot2; i++) if (b[i].cost <= d) { res2 = max(res2, b[i].val); if (flag == 1) flag++; } if (flag == 2) ans = max(res1 + res2, ans); for (int i = 1; i <= tot1; i++) pre[i] = max(pre[i - 1], a[i].val); for (int i = 2; i <= tot1; i++) { int l = 1, r = i - 1, p = 1; while (l <= r) { int mid = (l + r) >> 1; if (a[mid].cost <= c - a[i].cost) p = mid, l = mid + 1; else r = mid - 1; } if (a[i].cost + a[p].cost <= c) ans = max(ans, a[i].val + pre[p]); } for (int i = 1; i <= tot2; i++) pre[i] = max(pre[i - 1], b[i].val); for (int i = 2; i <= tot2; i++) { int l = 1, r = i - 1, p = 1; while (l <= r) { int mid = (l + r) >> 1; if (b[mid].cost <= d - b[i].cost) p = mid, l = mid + 1; else r = mid - 1; } if (b[i].cost + b[p].cost <= d) ans = max(ans, b[i].val + pre[p]); } printf("%d", ans); return 0; }