题解 P5078 【Tweetuzki 爱军训】

· · 题解

首先我们可以第一遍全部让学生出列

这样答案就会是\sum^n_{i=1}w[i]*i

( sum[ i ]为 1 到 i 的 w[ i ] 的前缀和)

当第i位同学第二批出列时，贡献就会变化 - (sum [ n ] - sum [ i ]) + (n - i) * w [ i ]

(自己想想为什么)

然后就很简单了

贡献为正，第二批

贡献为负，第一批

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
const int N = 5000010;

int n, w[N], sum[N], ans, a_1[N], a_2[N];

signed main () {
    scanf("%lld", &n);
    for(int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]), sum[i] = sum[i - 1] + w[i], ans += w[i] * i, a_1[i] = 1;
    for(int i = 1; i <= n; i ++ ) {
        if((n - i) * w[i] - (sum[n] - sum[i]) > 0) {
            ans += (n - i) * w[i] - (sum[n] - sum[i]);
            a_1[i] = 0; a_2[i] = 1;
        }
    }
    printf("%lld\n", ans);
    for(int i = 1; i <= n; i ++ ) if(a_1[i]) printf("%lld ", w[i]);
    for(int i = n; i >= 1; i -- ) if(a_2[i]) printf("%lld ", w[i]);
    return 0;
}