思路与算法

按推销疲劳降序，答案要么前k大本身，要么前k-1大加一户额外远端。前缀和、前缀最远距离及后缀(2S+A)极值一次计算所有k。

按上述模型建立状态或枚举对象，依代码中的顺序处理输入并输出完整答案。

正确性说明

对任意选择k户的集合，设它的最远户为j。固定j后其他k-1户为使疲劳最大应取剩余人的k-1大A。按A降序排序，若j在前k大中，则集合由前k大即可达到至少同样的销售和与最远距离；若j不在前k-1大中，其最佳值为前k-1大A之和加A[j]+2S[j]。因此两个候选分类覆盖所有最优解，前后缀聚合精确求其最大值。

复杂度

O(n log n)时间、O(n)空间，含排序下标、三组前后缀数组及n个答案。

易错点

选X户不允许增加多余往返；路程永远是最远距离的两倍，而不是逐户距离相加。距离可重复，A排序并列任意。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<long long> s(n), a(n);
    for (auto &x : s)
        cin >> x;
    for (auto &x : a)
        cin >> x;
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int x, int y) {
        return a[x] > a[y];
    });
    vector<long long> su(n + 1), far(n + 1), tail(n + 1, LLONG_MIN / 4);
    for (int i = 0; i < n; i++) {
        su[i + 1] = su[i] + a[p[i]];
        far[i + 1] = max(far[i], s[p[i]]);
    }
    for (int i = n - 1; i >= 0; i--)
        tail[i] = max(tail[i + 1], 2 * s[p[i]] + a[p[i]]);
    for (int k = 1; k <= n; k++)
        cout << max(su[k] + 2 * far[k], su[k - 1] + tail[k - 1]) << "\n";
}