洛谷 P5078 Tweetuzki 爱军训

题目连接

很明显，1e6的范围，要么nlgn要么O(n)

nlgn的话可能会想到借助一些数据结构，我并没有想到这种做法

对于这种题，O(n)的做法要么是线性递推，要么就应该是贪心了

考虑这道题我们怎么贪心

如果可以走无数个来回的话，那很明显我们可以从小到大依次取出，一定是最大的

可惜只能走一个来回

那么我们来看看只能走一个来回的话，有什么特性

对于第i个同学，要么是去的时候取出，要么是回来的时候取出，我们来考虑一下这有什么区别

当第i个同学为从去的时候取出变为回来的时候取出，多做的贡献就是排名差乘上他的权值

那么他会对那些同学造成影响呢？由于教官的路线是一个来回，我们不妨破环成链来考虑一下。

我们会发现第i个同学对应着两个位置——\(i\)和\(2n-i+1\)，设i为去的时候去的时候取，\(2n-i+1\)为回来取，那么如果我们将去的时候取换成回来取，会造成\([i+1,2n-i]\)之间的点排名整体前移1，也就是说如果第i名同学滞后取出，会造成\(-\sum_{k=i+1}^n w[k]\)的贡献，这个很明显可以用前缀和或后缀和O(1)算出

那么很明显了，如果i同学滞后选择额外产生的贡献严格大于零（因为要求相同情况序号字典序最小）那么我们就可以最后再选择他。

那么我们就可以直接贪心求方案，用双指针记录目前还没有确认的出列顺序的左右端点

没明白就看代码吧

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cctype>

#ifdef ONLINE_JUDGE

#define printf(o"\n") printf("I AK IOI\n")

#define printf(o) printf("I AK IOI")

#endif

#define ll long long

#define gc getchar

#define maxn 1000005

using namespace std;

inline ll read(){

	ll a=0;int f=0;char p=gc();

	while(!isdigit(p)){f|=p=='-';p=gc();}

	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}

	return f?-a:a;

}

int n,l,r;

ll ans,a[maxn],b[maxn],c[maxn];

int main(){

	n=read();l=1,r=n;

	for(int i=1;i<=n;++i){

		a[i]=read();

		b[i]=a[i]+b[i-1];    //前缀和

	}

	for(int i=1;i<=n;++i){

		ll jia=a[i]*(r-l);    //表示滞后取出产生的正贡献

		if(jia>b[n]-b[i]){  //大于负贡献也就是大于零

			c[r]=i;

			ans+=(ll)a[i]*r;

			--r;

		}

		else{    //否则正常取出

			c[l]=i;

			ans+=(ll)a[i]*l;

			++l;

		}

	}

	printf("%lld\n",ans);

	for(int i=1;i<=n;++i)

		printf("%lld ",a[c[i]]);    //c数组记录的只是下标，可别直接输出c数组

	return 0;

}

抄题解的猜猜我代码能不能AC（滑稽

巴特西

洛谷 P5078 Tweetuzki 爱军训

最新文章

热门文章