题解 P5078 【Tweetuzki 爱军训】

· · 题解

题目连接

体验++

我们首先从确定算法着手

n=1e6

根据常识,我们可以选择的有O(nlogn) or O(n)

同样根据常识O(nlogn)的玩意儿有二分,线段树等等

$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(' ');
    }
}