很明显，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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #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 1000005using 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（滑稽