自动搬运

查看原文

来自洛谷，原作者为

	Sirkey AFOed||安和昴男朋友

搬运于2025-08-24 22:33:07，当前版本为作者最后更新于2023-03-11 16:16:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考试考到了，只得了 $50$，忏悔一下。

我们可以 $O( 1 )$ 的求出开当前这个门所需要的时间：

ans1+=(a[i]+n-past1)%n

得记录一下前一个的状态，这里用的是 $past$。

我们可以说这是一个周期问题。但是这个循坏是特殊的，第一次和后来的是不相同的，所以我们要求两次。

区别在于，第一次的开始状态是 $1$，后面会变成 a[n]。

我们用 $ans1$ 记录首轮，到 $t$ 次就退出。

另为用 $ans$ 数组记录其他次数，用数组方便我们求不在整数的情况。

	for(int i=1; i<=n; i++) {
		ans[i]=ans[i-1]+(a[i]-past+n)%n;
		ans1+=(a[i]+n-past1)%n;
		past=a[i],past1=a[i];
		if(i==t) {
			cout<<ans1;
			return 0;
		}
	}

然后求一下，后面的轮数，加在 $ans1$ 上就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int MX=1e5+10;
long long n,t,a[MX],past=1,past1,ans[MX],ans1;
void init() {
	cin>>n>>t;
	for(int i=1; i<=n; i++) {
		int kkk;
		cin>>kkk;
		a[kkk]=i;
	}
}
int main() {
	init();
	past=a[n],past1=1;
	for(int i=1; i<=n; i++) {
		ans[i]=ans[i-1]+(a[i]-past+n)%n;
		ans1+=(a[i]+n-past1)%n;
		past=a[i],past1=a[i];
		if(i==t) {
			cout<<ans1;
			return 0;
		}
	}
	int wl=t/n-1;
	ans1+=wl*ans[n]+ans[t%n];
	cout<<ans1;
	return 0;
}

——end——