把奖金递推看成两机流水作业，使用 Johnson 法则分组排序后线性模拟。
OJ: luogu
题目 ID: P2123
难度:普及+/提高
标签:贪心排序调度
日期: 2026-06-22 20:43
题意
有 n 位大臣，每人有两个数 a_i,b_i。排好顺序后：
text
c_1 = a_1 + b_1
c_2 = max(a_1 + b_1, a_1 + a_2) + b_2 = max(a_1 + b_1 + b_2, a_1 + a_2 + b_2)
c_3 = max(c_2, a_1 + a_2 + a_3) + b_3 = max(a_1 + b_1 + b_2, a_1 + a_2 + b_2, a_1 + a_2 + a_3) + b_3 = max(a_1 + b_1 + b_2 + b_3, a_1 + a_2 + b_2 + b_3, a_1 + a_2 + a_3 + b_3)
c_i = max(c_{i-1}, a_1 + ... + a_i) + b_i要求重新排序，使获得奖金最多的大臣奖金尽量小。
因为 c_i 不会下降，最大值就是最后的 c_n。
思路
先看一个可以直接验证想法的朴素解：
cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10;
struct Person {
long long left_num;
long long right_num;
};
int n;
Person people[MAXN];
int order_id[MAXN];
long long calc_order() {
long long prefix_left = 0;
long long last_reward = 0;
for (int i = 0; i < n; i++) {
int id = order_id[i];
prefix_left += people[id].left_num;
last_reward = max(last_reward, prefix_left) + people[id].right_num;
}
return last_reward;
}
void solve_case() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> people[i].left_num >> people[i].right_num;
order_id[i] = i;
}
long long ans = -1;
do {
long long now = calc_order();
if (ans == -1 || now < ans) {
ans = now;
}
} while (next_permutation(order_id, order_id + n));
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve_case();
}
return 0;
}暴力会枚举所有排列，计算每个排列的 c_n，取最小。这个做法只能用于小数据。
观察递推式：
text
c_i = max(c_{i-1}, prefix_a) + b_i它和两台机器流水作业完全一样：
- 第一阶段耗时是
a_i； - 第二阶段耗时是
b_i； - 第二阶段开始前，必须等当前任务第一阶段完成，也必须等上一个任务第二阶段完成。
所以可以使用 Johnson 法则：
- 若
a_i <= b_i，放在前半段，并按a_i升序； - 若
a_i > b_i，放在后半段，并按b_i降序。
排好后从前到后模拟即可。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20005;
struct Person {
long long left_num;
long long right_num;
};
int n;
Person people[MAXN];
bool cmp_person(const Person &x, const Person &y) {
bool x_front = x.left_num <= x.right_num;
bool y_front = y.left_num <= y.right_num;
if (x_front != y_front) {
return x_front > y_front;
}
if (x_front) {
return x.left_num < y.left_num;
}
return x.right_num > y.right_num;
}
void solve_case() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> people[i].left_num >> people[i].right_num;
}
sort(people + 1, people + n + 1, cmp_person);
long long prefix_left = 0;
long long last_reward = 0;
for (int i = 1; i <= n; i++) {
prefix_left += people[i].left_num;
last_reward = max(last_reward, prefix_left) + people[i].right_num;
}
cout << last_reward << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve_case();
}
return 0;
}复杂度
排序复杂度为：
text
O(n log n)模拟为
总结
本题看起来像国王游戏，但排序规则不同。
递推式本质是两机流水作业，直接套 Johnson 法则：前半段按 a 升序，后半段按 b 降序。排序后线性模拟最后的奖金即可。