P7792

Sirkey · 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——