这道题是一个动态规划的题目。
我们首先令 \(f_{i,j}\) 为在前 \(i\) 家住户中选了 \(j\) 家住户，那么转移为 $$ans_j=\max(f_{i,j}+2S_i)$$。
那么如果我们按照上面打的话，我们会 TLE。
紧接着，我们可以使用后缀最大值将时间复杂度变为 \(\mathcal O(n)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 101000;
struct people {int a, s, id;
} p[N];
int n, suf[N], sum[N];
bool operator < (const people &a, const people &b) {return a.a > b.a;
}
int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &p[i].s);p[i].id = i;}for (int i = 1; i <= n; i++)scanf("%d", &p[i].a);for (int i = n; i >= 1; i--)suf[i] = max(suf[i + 1], 2 * p[i].s + p[i].a);//后缀最大值，在做某些题目，是要将suf清空的。sort(p + 1, p + n + 1);int smax = -1, id = -1;for (int X = 1; X <= n; X++) {sum[X] = sum[X - 1] + p[X].a;if (p[X].s > smax)smax = p[X].s, id = p[X].id;printf("%d\n", max(sum[X] + 2 * smax, sum[X - 1] + suf[id + 1]));}
}