题目链接：https://ac.nowcoder.com/acm/contest/243/A
题目大意：
略
分析：
方法就是把疲劳值从小到大排个序，然后从尾部开始一个一个取，当选到第i（i >= 2）个时有2种取法：一是取，那么X = i的答案就是[n-i+1,n]区间的疲劳值求和并加上其中最大距离的2倍；二是不取，那么答案便是[n-i+2,n]区间的疲劳值求和并加上[1,n-i]区间中（疲劳值+距离的2倍）最大的一个，为什么一定是前面那个最大？因为如果最大距离在[n-i+2,n]中，那显然是选取n-i的地方更增加疲劳值。2种取法取个最大即可。
最大的疑问是，为什么X=i时的最优解一定是建立在[n-i+2,n]区间中的数全部取完之后呢？
证明如下：
当i = 2时，第n个数是必取的，可以用反证法证明：假设取第x,y(x<y<n)个数时疲劳值最大，于是可以将其中一个不对距离贡献疲劳值的数换成第n个数，这样，无论最大距离是否更新，都出现了一个更优的解，与假设矛盾。
当i > 2时，也可以用反证法证明：假设在[n-i+2,n]中取m(m<i)个数，在[1,n-i+1]中取i-m个数的组合才是最优的。可以分2种情况：（1）最大距离在[1,n-i+1]区间中，那么[1,n-i+1]区间非最大距离的数都可以用[n-i+2,n]中的数代替，显然可以有更优的解。（2）最大距离在[n-i+2,n]区间中，显然这i个数全部选后i个数是最优的，因为前面的数不对距离有所贡献。综上，与假设矛盾。
代码如下：
#include <bits/stdc++.h>
using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define rFor(i,t,s) for (int i = (t); i >= (s); --i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
#define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) #define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl #define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin()) #define ms0(a) memset(a,0,sizeof(a))
#define msI(a) memset(a,inf,sizeof(a)) #define pii pair<int,int>
#define piii pair<pair<int,int>,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second inline int gc(){
static const int BUF = 1e7;
static char buf[BUF], *bg = buf + BUF, *ed = bg; if(bg == ed) fread(bg = buf, , BUF, stdin);
return *bg++;
} inline int ri(){
int x = , f = , c = gc();
for(; c<||c>; f = c=='-'?-:f, c=gc());
for(; c>&&c<; x = x* + c - , c=gc());
return x*f;
} typedef long long LL;
const int maxN = 1e5 + ; int n;
int dist[maxN], cost[maxN];
int suffixMax[maxN]; //记录dist的后缀最大值
int f[maxN]; // f[i]表示当X=1时在1~i范围内只选择1家住户的最优解
int prefixSum[maxN]; // cost的前缀和 int getSum(int x, int y){
return x < y ? prefixSum[y] - prefixSum[x] : ;
} void mergeSort(int l, int r){
if(l >= r) return;
int mid = (l+r) >> ; mergeSort(l, mid);
mergeSort(mid+, r); int tmp1[r-l+], tmp2[r-l+];
int i = l, j = mid + , k = ; while(i <= mid && j <= r){
if(cost[i] > cost[j] || cost[i] == cost[j] && dist[i] > dist[j]){
tmp1[k] = cost[j];
tmp2[k++] = dist[j++];
}
else{
tmp1[k] = cost[i];
tmp2[k++] = dist[i++];
}
}
while(i <= mid){
tmp1[k] = cost[i];
tmp2[k++] = dist[i];
++i;
}
while(j <= r){
tmp1[k] = cost[j];
tmp2[k++] = dist[j];
++j;
} rep(i, k){
cost[i+l] = tmp1[i];
dist[i+l] = tmp2[i];
}
} int main(){
scanf("%d", &n);
For(i, , n) dist[i] = ri();
For(i, , n) cost[i] = ri(); mergeSort(, n);
rFor(i, n, ) suffixMax[i] = max(suffixMax[i+], dist[i]); For(i, , n) f[i] = max(f[i-], cost[i] + dist[i]*); For(i, , n) prefixSum[i] = prefixSum[i-] + cost[i]; rFor(i, n, ) printf("%d\n", max(getSum(i, n) + f[i], getSum(i-, n) + *suffixMax[i]));
return ;
}