1 条题解
-
0
C++ :
#include <cstdio> #include <algorithm> using namespace std; struct P { int a, b; }; static P p[1005]; /* 按 (b 降序, a 降序):b 大的先吃能把「进食权」撑大,是使前缀和最大的排法。 吃第 j 个之前需要有进食权(rights = 1 + Σ_{i<j}(b_i-1) >= 1)。 a >= 0 ⇒ 取得越多越好,所以取满足全部前缀和 >= 0 的最长前缀。 */ bool cmp(const P &x, const P &y){ if(x.b != y.b) return x.b > y.b; return x.a > y.a; } int main(){ int n; if(scanf("%d", &n) != 1) return 0; for(int i = 0; i < n; i++) scanf("%d %d", &p[i].a, &p[i].b); sort(p, p + n, cmp); long long rights = 1, ans = 0; for(int i = 0; i < n; i++){ if(rights < 1) break; ans += p[i].a; rights += p[i].b - 1; } printf("%lld\n", ans); return 0; }
- 1
信息
- ID
- 2580
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者