Codeforces Round #421 (Div. 2)D - Mister B and PR Shifts(模拟)

传送门

题意

给出n个数，计算在进行n-1次右移中\(min\sum_{i=1}^nabs(p_i-i)\)

分析

我们设置cnt[p[i]-i]为一个数p[i]与它标准位置（如1的标准位置为1）的左偏差，用L记录一个数在标准位置左边/上的个数，R为在右边的个数，关键在于n-1次移动中如何更新\(min\sum_{i=1}^nabs(p_i-i)\)

先不考虑末尾移到第一位，如果右移一位，那么有cnt[i]个元素滚到标准位置的右边了，那么L-=cnt[i],R+=cnt[i],对于答案的贡献整体来看，每次都会减少L,增加R（请仔细思考）。接下来考虑末尾的元素跑到第一位，毫无疑问L++,R--,从(n,p[n-i])跑到(1,p[n-i]对于答案的贡献为(p[n-i]-1)+(n-p[n-i)。（请仔细思考），同时由于多减了1（右移L时未把末尾元素放到第一位),所以sum要加1，最后考虑末尾p[n-i]移到n-i的花费也要++，故cnt[p[n-i]+i]++，不妨列几个数试验试验。（请仔细思考），每次更新答案

相似blog

Jaihk662

Joovo

trick

代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

//#pragma comment(linker, "/STACK:102400000,102400000")

//inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

const int maxn=1e6+10;

int n,L,R;

int p[maxn],cnt[maxn*2];//记录与实际位置偏差的距离，如p[2]=3  那么与实际位置3偏差1

ll ans,sum;

int main()

{

    scanf("%d",&n);

    F(i,1,n)

    {

    	scanf("%d",p+i);sum+=abs(p[i]-i);

    	if(p[i]>=i) cnt[p[i]-i]++,L++;else R++;//L表示在实际位置的左边/上的数的个数，R表示在实际位置的右边的数的个数

    }

    ans=sum;

    int loc=0;

    R(i,0,n-1)//从p[n]枚举到p[2]

    {

    	L=L-cnt[i]+1,R=R+cnt[i]-1;//表示做第i+1次偏移对结果的影响，每次移动L减少cnt[i]，R增加cnt[i]，由于末尾元素移到第一位，故R--,L++

    	cnt[(p[n-i]+i)>n?(p[n-i]+i)%n:(p[n-i]+i)]++;//表示p[n-i]移到实际位置p[n-i]需要的花费，举个例子 3 2 4 5 1，一次op后1 3 2 4 5，cnt[1]++;二次op后5 1 3 2 4，cnt[6]++

    	sum=sum-L+R-abs(n-p[n-i])+abs(p[n-i]-1)+1;//最后一个数从abs(p[n-i]-n)变成abs(p[n-i]-1),表示从末尾到1的花费

    	if(sum<ans) ans=sum,loc=i+1;//更新答案

    }

    printf("%I64d %d\n",ans,loc);

    return 0;

}

巴特西

Codeforces Round #421 (Div. 2)D - Mister B and PR Shifts(模拟)

传送门

题意

分析

trick

代码

最新文章

热门文章