标签：尝试 洛谷 int 题解 P7792 long 次数 钥匙 扇门

洛谷P7792 KRIZA 题解 C++

题目概述：

题目传送门

Sisyphus 在一个圆形的房间里，房间内有 n 扇锁着的门，他有 n 把钥匙，其中第 i 把钥匙对应第 $v_i$ 扇门，遇到不匹配的钥匙就放到钥匙扣的另一边。他需要解锁所有的门。Sisyphus 沿着门编号顺序，每次到一扇门前就找到第 i 把钥匙尝试打开门，直到找到正确的钥匙，然后把门再锁上，一直到他第 k 次成功解锁为止。

数据范围：

• 对于 40% 的数据，1 ⩽ n , k ⩽ 10^3。

• 对于 \(60\%\) 的数据，\(1 ⩽ n , k ⩽ 5 \times 10^4\)。

• 对于 \(100\%\) 的数据，\(1 ⩽ n , k ⩽ 5 \times 10^4\)。

思路：

看到此题，第一反应肯定是暴力，模拟到每一扇门前尝试每一把钥匙，这样的时间复杂度为 $O(nk)$，肯定过不了，提交只有 $24pts$。

这时候我们可以想想优化。

我们只需要集中一下注意力，不难发现，对于尝试每一圈的 \(n\) 扇门，其实这是一个循环的过程，所以我们只需要遍历一圈即可。

我们可以用 \(a_i\) 表示从第 \(1\) 扇门到第 \(i-1\) 扇门尝试的次数 （是不是有点像前缀和？），然后我们维护 \(p\) 表示当前已经选到的钥匙编号，然后从 \(2\) 到 \(n+1\) 遍历，对于每一扇门，更新 \(p\) 和 \(a_i\) 的值，最后可以计算出试完第 \(k\) 扇门的尝试次数，即：

• \(a[n]×(k ÷ n)+a[k\mod n]\)

这是什么意思？很好理解，我们已经计算出了每圈的尝试次数，我们用次数乘上圈数就是整圈的尝试次数，然后我们再加上剩余不足一圈的尝试次数，就是答案了。

可能还有人要问：为什么是从 $2$ 到 $n+1$ 遍历？

这也很好理解，因为 $a_i$ 表示的是从第 $1$ 扇门到第 $i-1$ 扇门尝试的次数。对于第 $i-1$ 扇门，从第 $1$ 扇门到这扇门的尝试次数等于上一次的尝试次数加上这一次的尝试次数。

Tips:注意两个坑：

1. 下一扇门的钥匙编号可能到下一圈，更新时要判断。

2. k 一定要减一，因为有 \(k\mod n = 0\) 的情况，最后可能会多算。

3. 为了方便处理，本蒟蒻把输入的 \(v_i\) 改成了表示第 i 扇门的钥匙编号。

\(Code\)

#include<bits/stdc++.h>
using namespace std;
long long v[100001],a[100001];
int n,k;
int p,sum;
long long ans=0;//保险起见，开个long long
int main()
{
	cin>>n>>k;
	k--;
	for(int i=1;i<=n;i++) 
	{
	int x;
	cin>>x;
	v[x]=i;
	}//输入不用说
	ans=v[1]-1;//这句很重要：ans的初始值
	p=v[1];//p从1开始
	v[n+1]=v[1];//第n+1扇门就是第1扇门
	for(int i=2;i&lt;=n+1;i++)
	{
	if(v[i]>=p)a[i-1]=a[i-2]+v[i]-p;
	//钥匙的编号和当前的钥匙编号在一圈内：更新a数组：上一扇门加上这扇门需要尝试的次数
	else a[i-1]=a[i-2]+v[i]+n-p;
	//否则在下一圈
	p=v[i];//更新p
	}
	ans+=a[n]*(k/n)+a[k%n];//算答案
	cout<<ans;
	return 0;
}

后记

其实也没啥好说的

这是本蒟蒻的第一篇题解，

最后，若有错误，还请各位dalao指出！

完结撒花

\(By\) \(FHenryh\)

标签：尝试,洛谷,int,题解,P7792,long,次数,钥匙,扇门
From： https://www.cnblogs.com/FHenryh/p/solution-LG-P7792.html