Arc077_E Guruguru

题目大意

有$m$个点编号从小到大按照顺时针编成了一个环，有一枚棋子，每次移动可以选择顺时针移动到下一个或者直接移动到编号为$x$的点，现在有$n-1$次数操作，第$i$次要把棋子从第$A_i$移到第$A_{i+1}$号节点，可以在初始时自由设定$x$，求每次操作移动步数之和的最小值。

题解

$x$对一次移动有意义当且仅当$x$被直接操作经过不在起点上，其中贡献为$起点到终点的距离$+1$-$x$到终点的距离$。

考虑设$x$能减少多少代价，维护$x$取每一个位置时能使总代价减少多少，对于一段操作区间，当$x=l+1,x=l+2...x=r$的差异恰好是一段等差数列，首相为$0$，公差为$1$，可以使用二次差分解决，最后只需要枚举每一个位置记答案最值即可。

复杂度$O(n+m)$。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define M 200020

using namespace std;

namespace IO{

	const int BS=(1<<21)+3; LL Top=0; char Buffer[BS],*HD,*TL,SS[20];

	char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return (HD==TL)?EOF:*HD++;}

	int read(){

		int nm=0; char cw=Getchar(); for(;!isdigit(cw);cw=Getchar());

		for(;isdigit(cw);cw=Getchar()) nm=nm*10+(cw-'0'); return nm;

	}

} using namespace IO;

int n,m,dt[M]; LL tot,s[M],ans;

int main(){

	n=read(),m=read();

	for(register int last=read(),i=1,x;i<n;last=x,i++){

		x=read(),dt[last+2]++;

		if(last<x) dt[x+1]--,tot+=x-last,s[x+1]-=x-last-1;

		else tot+=x+m-last,dt[1]++,dt[x+1]--,s[1]+=m-last-1,s[x+1]-=m+x-last-1;

	} ans=tot;

	for(register int i=1;i<=m;i++) dt[i]+=dt[i-1],s[i]+=s[i-1]+dt[i],ans=min(ans,tot-s[i]);

	printf("%lld\n",ans); return 0;

}

巴特西

Arc077_E Guruguru

最新文章

热门文章