洛谷2672（数据处理技巧）

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <sstream>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <fstream>
#define ri readint()
#define gc getchar()
#define R(x) scanf("%d", &x)
#define W(x) printf("%d\n", x)
#define init(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define irep(i, a, b) for (int i = a; i >= b; i--)
#define ls p << 1
#define rs p << 1 | 1
using namespace std;

typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int inf = 0x3f3f3f3f;
const ll INF = 1e18;

/*****正文开始*****/

inline int readint() {//普通快读
    int x = 0, s = 1, c = gc;
    while (c <= 32) c = gc;
    if (c == '-')   s = -1, c = gc;
    for (; isdigit(c); c = gc)
        x = x * 10 + c - 48;
    return x * s;
}

const int maxn = 1e5 + 5;
struct family {
    int s, a;//s是距离，a是疲劳值

    family() {
    //初始值设为inf跟题意无关
    //只是笔者使用1～n的标号，这样从大到小排序时不用管下标为0了
    //其实不用搞这种麻烦事情的……
        s = a = inf;
    }

    bool operator < (const family b) const {
        return a > b.a;//按a值从大到小排
    }
};

int main() {
    int n = ri;//读入n
    vector<family> v(n + 1);//开数组
    //输入、按a排序
    rep(i, 1, n)    v[i].s = ri;
    rep(i, 1, n)    v[i].a = ri;
    sort(v.begin(), v.end());

    int maxpres[n+1];//前i个家庭中s值最大为多少
    int suma[n+1];//前i个家庭a值的前缀和
    int maxsufall[n+2];//从i往后（包括i）的家庭中最大的s+2*a为多少，维护这个东西跟题目性质有关
    init(maxpres, 0), init(suma, 0), init(maxsufall, 0);//初始化为0

    //计算各个要维护的值
    rep(i, 1, n)    maxpres[i] = max(maxpres[i - 1], v[i].s);
    rep(i, 1, n)    suma[i] = suma[i - 1] + v[i].a;
    irep(i, n, 1)   maxsufall[i] = max(maxsufall[i + 1], v[i].a + v[i].s * 2);

    vector<int> ans;//要么是直接取前i个，要么取i-1个加上后面取一个
    rep(i, 1, n)    ans.push_back(max(suma[i] + 2 * maxpres[i], suma[i - 1] + maxsufall[i]));
    for (int i : ans)   W(i);//输出