算贡献就是在普通思路上交换循环数,或是交换求和符号的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; }
标签:typedef,Chinese,Restaurant,int,long,循环,abc268 From: https://www.cnblogs.com/F-beginner/p/17372571.html