题目链接：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个数是最优的，因为前面的数不对距离有所贡献。综上，与假设矛盾。
代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define rep(i,n) for (int i = 0; i < (n); ++i) 5 #define For(i,s,t) for (int i = (s); i <= (t); ++i) 6 #define rFor(i,t,s) for (int i = (t); i >= (s); --i) 7 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 8 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) 9 10 #define pr(x) cout << #x << " = " << x << " " 11 #define prln(x) cout << #x << " = " << x << endl 12 13 #define ALL(x) x.begin(),x.end() 14 #define INS(x) inserter(x,x.begin()) 15 16 #define ms0(a) memset(a,0,sizeof(a)) 17 #define msI(a) memset(a,inf,sizeof(a)) 18 19 #define pii pair<int,int> 20 #define piii pair<pair<int,int>,int> 21 #define mp make_pair 22 #define pb push_back 23 #define fi first 24 #define se second 25 26 inline int gc(){ 27 static const int BUF = 1e7; 28 static char buf[BUF], *bg = buf + BUF, *ed = bg; 29 30 if(bg == ed) fread(bg = buf, 1, BUF, stdin); 31 return *bg++; 32 } 33 34 inline int ri(){ 35 int x = 0, f = 1, c = gc(); 36 for(; c<48||c>57; f = c=='-'?-1:f, c=gc()); 37 for(; c>47&&c<58; x = x*10 + c - 48, c=gc()); 38 return x*f; 39 } 40 41 typedef long long LL; 42 const int maxN = 1e5 + 7; 43 44 int n; 45 int dist[maxN], cost[maxN]; 46 int suffixMax[maxN]; //记录dist的后缀最大值 47 int f[maxN]; // f[i]表示当X=1时在1~i范围内只选择1家住户的最优解 48 int prefixSum[maxN]; // cost的前缀和 49 50 int getSum(int x, int y){ 51 return x < y ? prefixSum[y] - prefixSum[x] : 0; 52 } 53 54 void mergeSort(int l, int r){ 55 if(l >= r) return; 56 int mid = (l+r) >> 1; 57 58 mergeSort(l, mid); 59 mergeSort(mid+1, r); 60 61 int tmp1[r-l+1], tmp2[r-l+1]; 62 int i = l, j = mid + 1, k = 0; 63 64 while(i <= mid && j <= r){ 65 if(cost[i] > cost[j] || cost[i] == cost[j] && dist[i] > dist[j]){ 66 tmp1[k] = cost[j]; 67 tmp2[k++] = dist[j++]; 68 } 69 else{ 70 tmp1[k] = cost[i]; 71 tmp2[k++] = dist[i++]; 72 } 73 } 74 while(i <= mid){ 75 tmp1[k] = cost[i]; 76 tmp2[k++] = dist[i]; 77 ++i; 78 } 79 while(j <= r){ 80 tmp1[k] = cost[j]; 81 tmp2[k++] = dist[j]; 82 ++j; 83 } 84 85 rep(i, k){ 86 cost[i+l] = tmp1[i]; 87 dist[i+l] = tmp2[i]; 88 } 89 } 90 91 int main(){ 92 scanf("%d", &n); 93 For(i, 1, n) dist[i] = ri(); 94 For(i, 1, n) cost[i] = ri(); 95 96 mergeSort(1, n); 97 rFor(i, n, 1) suffixMax[i] = max(suffixMax[i+1], dist[i]); 98 99 For(i, 1, n) f[i] = max(f[i-1], cost[i] + dist[i]*2); 100 101 For(i, 1, n) prefixSum[i] = prefixSum[i-1] + cost[i]; 102 103 rFor(i, n, 1) printf("%d ", max(getSum(i, n) + f[i], getSum(i-1, n) + 2*suffixMax[i])); 104 return 0; 105 }