【不知道怎么分类】CF 819B Mister B and PR Shifts

题目内容

洛谷链接

定义一个全排列\(p_i\)的偏移值为\(\sum_{i=1}^{n}|p[i]-i|\)。
给你一个全排列，你可以从后面拿\(k\in[0,n-1]\)个数放在前面，使得该全排列的偏移值最小，输出这个偏移值和\(k\)，如果有多个\(k\)任意输出一个。
\(n\le 10^6\)

样例1输入

3

1 2 3

样例1输出

0 0

//不需要调整

样例2输入

3

2 3 1

样例2输出

0 1

//Shift一次，变为1 2 3

样例3输入

3

3 2 1

样例3输出

2 1

//Shift一次，变为1 3 2，偏移值为2

思路

每Shift一次，\(p[i]-i\le 0\)的偏移值会+1，而\(p[i]-i>0\)的偏移值会-1。也就是说,每Shift一次后正数的贡献会减去正数数量,而正数数量会减去1的数量;非正数数量的贡献会加上非正数数量,而非正数数量会加上1的数量。

代码

#include<stdio.h>

#include<stdlib.h>

typedef long long ll;

const int maxn=2e6+10;

int n,l,r,k;

ll ans,sum;

int p[maxn],cnt[maxn];

int main(){

    scanf("%d",&n);

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

        scanf("%d",&p[i]);

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

        sum+=abs(p[i]-i);

        if(p[i]>=i){

            l++;

            cnt[p[i]-i]++;

        }

        else r++;

    }

    ans=sum;

    for(int i=0;i<n-1;i++){//注意循环范围

        l-=cnt[i];

        r+=cnt[i];

        sum=sum-l+r-abs(p[n-i]-n-1)+p[n-i]-1;

        cnt[p[n-i]+i]++;

        l++;r--;

        if(sum<ans){

            ans=sum;

            k=i+1;

        }

    }

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

    return 0;

}

巴特西

【不知道怎么分类】CF 819B Mister B and PR Shifts

题目内容

样例1输入

样例1输出

样例2输入

样例2输出

样例3输入

样例3输出

思路

代码

最新文章

热门文章