526互联

abc268 C - Chinese Restaurant

发布时间 2023-05-04 21:34:30作者: 星陨光逝

C - Chinese Restaurant 

算贡献就是在普通思路上交换循环数，或是交换求和符号的2边的个数，来达到优化和解题的目的

对于该题，我刚开始的想法是循环旋转次数，再去查看符合要求的菜的个数，这样是O^2的

于是我们交换循环数，先去循环每个菜，我们发现每个菜实际上只对3个循环次数有贡献，于是时间复杂度就变成了O*3

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int>p(n),cnt(n);
    for(int i=0;i<n;i++)cin>>p[i];
    for(int i=0;i<n;i++){
        for(int j=p[i]-1;j<=p[i]+1;j++){
            cnt[(j-i+n)%n]++;
        }        
    }
    int ans=0;
    for(int i=0;i<n;i++)ans=max(ans,cnt[i]);
    cout<<ans<<endl;
    return 0;
}