P7792 [COCI2014-2015#7] KRIZA 题解

· · 题解

P7792 [COCI2014-2015#7] KRIZA 题解

我们可以先暴力模拟，拿到 32 分，时间复杂度 O(n \times k)

不难发现，试错太浪费时间了。我们可以先预处理好第 i 个锁至第 i+1 个所要把一把错误的钥匙放在门锁里多少次。这样会快很多，可以拿到 48 分，时间复杂度 O(n+k)。

根据第二个样例可知，同样的一扇门可能会被打开多次。所以，我们可以直接预处理出门被打开的次数就行了，不需要一个一个门开，这样又会快很多，可以拿到满分，时间复杂度 O(n)。

注意要开 long long，否则只能拿 48 分。

满分code:

为什么我的代码只有十行？
#include<bits/stdc++.h>
long long n,m,a[100001],pos[100001],dis[100001],sum[100001];//pos[] 是每个门的钥匙的位置，用来计算 dis[]。dis是每两个门的钥匙在坠子上的距离。sum[] 是 dis[] 的前缀和。
int main(){
    std::cin>>n>>m;
    for(int i=0;i<n;i++) std::cin>>a[i];
    for(int i=0;i<n;i++) pos[a[i]-1]=i;
    for(int i=1;i<=n;i++) dis[i]=(pos[i%n]-pos[i-1]+n)%n;//计算距离。
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+dis[i];//前缀和预处理。
    std::cout<<pos[0]+(m-1)/n*sum[n]+sum[(m-1)%n];
}
Thanks