自动搬运

查看原文

来自洛谷，原作者为

	Lysus 。。。

搬运于2025-08-24 22:06:55，当前版本为作者最后更新于2020-10-23 14:11:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

这样答案就会是$\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;
}