很明显，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"
") printf("I AK IOI
")
#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
",ans);
for(int i=1;i<=n;++i)
printf("%lld ",a[c[i]]); //c数组记录的只是下标，可别直接输出c数组
return 0;
}
抄题解的猜猜我代码能不能AC（滑稽