题解 P5078 【Tweetuzki 爱军训】

[题目连接](https://www.luogu.com.cn/problem/P5078) [体验++](https://www.cnblogs.com/the-Blog-of-Mikasa/p/13207290.html) ### 我们首先从确定算法着手 $ n=1e6 $ 根据常识,我们可以选择的有$O(nlogn) or O(n)$ 同样根据常识$O(nlogn)的玩意儿有二分,线段树等等$ $O(n)$的玩意儿有dp,贪心 $dp$我觉得起码要开二维才行,否则弄不出来的 那么就只剩下贪心和二分线段树之类的 首先二分线段树之类我是实在想不出怎么做 贪心倒是可以做出来 ### 思路 ~~XBB结束~~ 我们让他们第一次过去全部出队 回来的一趟再把他们拉回来再出队（雾 我们想想 比如一组数 1 2 3 4 5 6 把第**i**位拉出来放在最后 是不是只对$i+1->n$的排名有影响? 那么我们就更新...等等!这不就成$O(n^2)$了吗? 我们需要用聪明的方法来玄学优化这一个更新 明显,$i+1->n$排名均$--$ 那么我们用结合律搞一下,不就是减去$\sum_{j=i+1}^n a(j)吗$ 那么加一个前缀和优化一波 然后我们再用指针乱搞一下排名 就AC啦~ ``` #include<bits/stdc++.h> #define N 1001001 #define int unsigned long long using namespace std; inline int read( ){ int sum=0,ft=1; char ch=getchar( ); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar( ); if(ch=='-'){ ch=getchar( ); ft=-1; } while(ch>='0'&&ch<='9'){ sum=ch-'0'+(sum<<3)+(sum<<1); ch=getchar( ); } return ft*sum; } inline void print(int k){ if(!k)return; print(k/10); putchar(k%10+'0'); } int sum[N],n,a[N],pre[N],nex[N],last,xu[N]; inline void work(int k){ nex[last]=k; pre[nex[k]]=pre[k]; nex[pre[k]]=nex[k]; nex[k]=0; pre[k]=last; last=k; } signed main( ){ n=read( ); int i,j,ans=0,k; for(i=1;i<=n;i++){ nex[i]=i+1; pre[i]=i-1; k=read( ); sum[i]=k; a[i]=k; ans=ans+k*i; } last=n; nex[n]=0; for(i=n-1;i>=1;i--)sum[i]+=sum[i+1]; for(i=n;i>=1;i--) if((n-i)*a[i]>sum[i+1]){ ans+=(n-i)*a[i]-sum[i+1]; work(i); } print(ans); putchar('\n'); int ci=0,t; for(i=1;i<=n;i++) if(!pre[i]){ t=i; break; } while(t){ xu[++ci]=t; t=nex[t]; } for(i=1;i<=n;i++){ if(a[xu[i]])print(a[xu[i]]); else putchar('0'); putchar(' '); } } ```