按推销疲劳值降序排序后，用前缀和与后缀最大值维护「A 前缀和 + 2×最远距离」的两种贪心决策，对每个 X 取较大者。
OJ: roj
题目 ID: 3627
难度:普及
标签:贪心排序前缀和python
创建: 2026-10-02 11:36
更新: 2026-10-06 15:25
题目描述
死胡同入口一侧有 N 家住户，第 i 家距入口 S_i 米、推销可得疲劳值 A_i。对每个 X=1…N，从入口出发依次访问其中 X 家再原路返回，求「2×最远被访问距离 + 推销疲劳值之和」的最大值，并输出 N 行答案。输入第一行为 N，第二行为递增的 N 个 S_i，第三行为 N 个 A_i。样例 1 输入 5 / 1 2 3 4 5 / 1 2 3 4 5，输出 15 19 22 24 25。
思路
路径代价只由最远的住户决定，所以把选 X 家的最优方案按最远点分类。按 A 降序（A 相同则距离大者优先）排序，预处理前缀和 sum_i、前缀最远距离 q_i 和后缀最大值 h_i = max_{j≥i}(2S_j+A_j)，则每个 X 的答案为 max(sum_i + 2q_i, sum_{i-1} + h_i)，总复杂度 O(N log N)。
参考代码
Python 版：
python
import sys
def main() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
s_in = [next(data) for _ in range(n)] # 第 i 家到入口的距离 S_i
a_in = [next(data) for _ in range(n)] # 向第 i 家推销的疲劳值 A_i
# 按推销疲劳值 A 降序排序，A 相同则距离大者优先：
# 这样「排序前 i 项」恰好是「A 前 i 大中距离尽量大的那组」
sa = sorted(zip(s_in, a_in), key=lambda p: (-p[1], -p[0]))
s = [p[0] for p in sa]
a = [p[1] for p in sa]
# h[i] = max_{j>=i} (2*S_j + A_j)：最远点取到排序位置 >= i 时的最佳「路程+推销」贡献
h = [0] * (n + 2)
for i in range(n - 1, -1, -1):
h[i] = max(h[i + 1], 2 * s[i] + a[i])
ans: list[int] = []
prev = 0 # 前 X-1 大的 A 之和
pre = 0 # 前 X 大的 A 之和
qmax = 0 # 前 X 名中的最远距离
for i in range(n):
pre += a[i]
qmax = max(qmax, s[i])
# 决策一：最远点在前 i 名内 → pre + 2*qmax
# 决策二：舍弃第 i 名、改去更远的 j（>=i，按 A 序）→ prev + 2*S_j + A_j
ans.append(max(pre + 2 * qmax, prev + h[i]))
prev = pre
sys.stdout.write('\n'.join(map(str, ans)))
if __name__ == '__main__':
main()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-06 15:25
* update_at: 2026-10-06 15:25
*/
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
struct House {
ll s; // 到入口的距离 S
ll a; // 推销得到的疲劳值 A
};
int n;
House house[MAXN]; // 排序后的住户：按 A 降序，A 相同则距离大者优先
ll sumA[MAXN]; // sumA[i] = 排序后前 i 家 A 之和
ll farest[MAXN]; // farest[i] = 排序后前 i 家中最远的距离
ll suffixBest[MAXN]; // suffixBest[i] = max_{j >= i} (2*S_j + A_j)
// 按推销疲劳值 A 降序排序，A 相同时距离大者优先。
// 这样「排序前 i 项」恰好是「A 前 i 大里距离尽量大的那组」。
bool cmp_house(const House &x, const House &y) {
if (x.a != y.a) {
return x.a > y.a;
}
return x.s > y.s;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &house[i].s);
}
for (int i = 1; i <= n; i++) {
scanf("%lld", &house[i].a);
}
sort(house + 1, house + n + 1, cmp_house);
// 前缀和与前缀最远距离
for (int i = 1; i <= n; i++) {
sumA[i] = sumA[i - 1] + house[i].a;
farest[i] = max(farest[i - 1], house[i].s);
}
// 后缀最大值 h_i = max_{j >= i} (2*S_j + A_j)，表示从第 i 名往后任选一家当最远点的最佳贡献
suffixBest[n + 1] = 0;
for (int i = n; i >= 1; i--) {
ll cand = 2 * house[i].s + house[i].a;
suffixBest[i] = max(suffixBest[i + 1], cand);
}
// 对每个 X：要么最远点落在 A 前 X 大中，要么舍弃第 X 名换去更远处
for (int i = 1; i <= n; i++) {
ll plan1 = sumA[i] + 2 * farest[i];
ll plan2 = sumA[i - 1] + suffixBest[i];
printf("%lld\n", max(plan1, plan2));
}
return 0;
}