---
title: P5078 Tweetuzki 爱军训
type: 题解
tags:
  - 信息竞赛题解
  - 贪心
  - 前缀和
---

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

我们设 $pre_m = \sum^{m}_{i = 1}w_i$

则：
$$
delta = (k - n) \times w_k - (pre_n - pre_k)
$$
 如果 $delta < 0$，则说明第 $k$ 位上同学在教官反着走的时候出列，比在教官正着走时出列更优，则使得第 $k$ 为上的人出列即可。

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

```cpp
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$ 位置上的人，反着走时被选择，会对其他人的选择贪心判断造成影响。

考虑在我们想要选择 $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$ 单独选择后加起来。

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

那么贪心即可，代码超短：

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