Tweetuzki 爱军训
引言
本文更注重推导过程，无法理解其他题解的可以来这里看看。
解法
考虑贪心。
用 \(ans\) 表示最后的答案，在刚开始时假设全部都按 \(1 \to n\) 的顺序出列，则 \(ans = \sum^{n}_{i = 1} w_i \times i\)。
对第 \(k\) 个同学出列的价值变化考虑，有：
\[ans = \sum^{k - 1}_{i = 1} w_i \times i + \sum^{n}_{k + 1} w_i \times (i - 1) + n \times w_k \]我们计算初始的 \(ans\) 和变化后的 \(ans\) 值的差值：
\[delta = \sum^{n}_{i = 1} w_i \times i - \left( \sum^{k - 1}_{i = 1} w_i \times i + \sum^{n}_{k + 1} w_i \times (i - 1) + n \times w_k \right) \]\[= \sum^{n}_{i = 1} w_i \times i - \sum^{k - 1}_{i = 1} w_i \times i - \sum^{n}_{k + 1} w_i \times (i - 1) - n \times w_k \]\[= \sum^{n}_{i = k} w_i \times i - \sum^{n}_{i = k + 1} w_i \times i + \sum^{n}_{k + 1} w_i - n \times w_k \]\[= (k - n) \times w_k - \sum^{n}_{k + 1} w_i \times i \]我们设 \(pre_m = \sum^{m}_{i = 1}w_i\)
则：
\[delta = (k - n) \times w_k - (pre_n - pre_k) \]如果 \(delta < 0\)，则说明第 \(k\) 位上同学在教官反着走的时候出列，比在教官正着走时出列更优，则使得第 \(k\) 为上的人出列即可。
那么我们的核心代码就很好写了：
for(int k = 1;k <= n;k++){
if(pre[n] - pre[k] + (k - n) * w[k] < 0){
ans += -(pre[n] - pre[k] + (k - n) * w[k]);
id[k] = true;
}
}
证明
我们推导的时候会发现，有没有可能选择一个 \(k\) 位置上的人，反着走时被选择，会对其他人的\times\times选择贪心判断\times\times造成影响。
考虑在我们想要选择 \(k\) 位置上的人时，前面已经有一个 \(s\) 位置上的人被选了。（\(k > s\)）
则选择这两个后的 \(ans\) 会变为：
\[\sum^{s - 1}_{i = 1}w_i \times i + \sum^{k - 1}_{i = s + 1} w_i \times (i - 1) + \sum^{n}_{i = k + 1}w_i \times (i - 2) + w_s \times n + w_k \times (n - 1) \]那么 \(delta\) 会变为：
\[\sum^{n}_{i = 1} w_i \times i - \left(\sum^{s - 1}_{i = 1}w_i \times i + \sum^{k - 1}_{i = s + 1} w_i \times (i - 1) + \sum^{n}_{i = k + 1}w_i \times (i - 2) + w_s \times n + w_k \times (n - 1)\right) \]\[= \sum^{n}_{i = s} w_i \times i - \sum^{k - 1}_{i = s + 1} w_i \times (i - 1) - \sum^{n}_{i = k + 1} w_i \times (i - 2) - w_s \times n - w_k \times(n - 1) \]\[= \sum^{n}_{i = s} w_i \times i - \sum^{k - 1}_{i = s + 1} w_i \times i + \sum^{k - 1}_{i = s + 1}w_i - \sum^{n}_{i = k + 1} w_i \times i + \sum^{n}_{i = k + 1}2w_i - w_s \times n - w_k \times n + w_k \]\[= \left( \sum^{n}_{i = k} w_i \times i + w_s \times s \right) + (pre_{k - 1} - pre_s) - \sum^{n}_{i = k + 1}w_i * i + 2 \times (pre_n - pre_k) - w_s \times n - w_k \times n + w_k \]\[= w_k \times (k - n) + w_s \times (k - n) + (pre_n - pre_k) + (pre_n - pre_s) + w_k - (pre_{k - 1} - pre_k) \]\[= \{ (k - n) \times w_k - (pre_n - pre_k) \} + \{ (s - n) \times w_s - (pre_n - pre_s) \} \]那么我们发现，最后的式子可以拆成 \(s\) 单独选择和 \(k\) 单独选择后加起来。
同理可得，无论多少个数选择都不会对彼此造成影响，也就是说这些选择彼此是独立的。
那么贪心即可，代码超短：
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int MAXN = 1e6 + 7;
int n;
int w[MAXN];
bool id[MAXN];
int pre[MAXN];
int ans;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1;i <= n;i++) cin >> w[i],pre[i] = pre[i - 1] + w[i];
for(int i = 1;i <= n;i++) pre[i] = pre[i - 1] + w[i],ans += w[i] * i;
for(int k = 1;k <= n;k++){
if(pre[n] - pre[k] + (k - n) * w[k] < 0){
ans += -(pre[n] - pre[k] + (k - n) * w[k]);
id[k] = true;
}
}
cout << ans << endl;
for(int i = 1;i <= n;i++) if(!id[i]) cout << w[i] << " ";
for(int i = n;i >= 1;i--) if(id[i]) cout << w[i] << " ";
return 0;
}
done.
标签：pre,P5078,int,sum,ans,times,delta,Tweetuzki,军训 From： https://www.cnblogs.com/wyl123ly/p/18457120