w wyl123ly 的博客
MD

P5078 Tweetuzki 爱军训

4 KB 2026.10.11 原文件

Tweetuzki 爱军训

引言

本文更注重推导过程,无法理解其他题解的可以来这里看看。

解法

考虑贪心。

用 表示最后的答案,在刚开始时假设全部都按 的顺序出列,则 。

对第 个同学出列的价值变化考虑,有:

我们计算初始的 和变化后的 值的差值:

我们设

则:

如果 ,则说明第 位上同学在教官反着走的时候出列,比在教官正着走时出列更优,则使得第 为上的人出列即可。

那么我们的核心代码就很好写了:

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;
	}
}

证明

我们推导的时候会发现,有没有可能选择一个 位置上的人,反着走时被选择,会对其他人的选择贪心判断造成影响。

考虑在我们想要选择 位置上的人时,前面已经有一个 位置上的人被选了。()

则选择这两个后的 会变为:

那么 会变为:

那么我们发现,最后的式子可以拆成 单独选择和 单独选择后加起来。

同理可得,无论多少个数选择都不会对彼此造成影响,也就是说这些选择彼此是独立的。

那么贪心即可,代码超短:

#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.