abc268C

FiraCode · 2023-04-09 15:22:12 · 个人记录

abc268

题意:

有 N 个人从 0 开始编号， 按逆时针顺序间隔均匀地坐在转盘周围。 在开始时， 第 p_{i} 盘菜在第 i 个人的前面。

现在， 你可以进行以下操作 0 次或多次。

• 将转盘逆时针旋转 \frac{1}{N} 圈。也就是说， 旋转前在第 i 号人面前的盘子现在在 (i+1)\bmod N 号人面前了。

当你结束操作后，如果第 i 盘菜在第 (i-1)\bmod N 个人、第 i 个人或第 (i+1)\bmod N 个人面前，第 i 个人就会感到高兴。

请求出你最多能使多少人感到高兴。

思路:

因为让第i个人开心开心要把第i盘菜转到i-1,i,i+1。 那么我们就记f_i表示转i次开心的人数。 那么我们记第i盘菜转到i-1,i,i+1的步数分别记为cnt1,cnt2,cnt3，那么cnt_{cnt1}+1, cnt_{cnt2}+1, cnt_{cnt_3}+1，因为转cnt1,cnt2,cnt3次都可以让i开心。 最后我们枚举转多少次（因为转n次就转回来了，所以枚举到n就足够了），然后对cnt求个最大值就可以了。

注意：取模会有负数要特判一下(i-1)

\texttt{My Code:}

#include <bits/stdc++.h>
using namespace std;
int n;
int a[200010], cnt[200010];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    for (int i = 0; i < n; ++i) {
        cnt[(a[i] - 1 - i - 1 + n) % n]++;//转到i-1
        cnt[(a[i] - 1 - i + n) % n]++;//转到i
        cnt[(a[i] - i + n) % n]++;//转到i+1
    }
    int ans = 0;
    for (int i = 0; i < n; ++i)
        ans = max(ans, cnt[i]);
    printf("%d\n", ans);
    return 0;
}

\texttt{S08577} \texttt{Code}:

这个cnt_i表示转i次，正好转到面前的个数。 那么最后统计答案的就要在少转或多转一次（因为若和他想等的菜在i+1或i-1，那么在少/多转一次就能转到）

#include<iostream>
#include<cstring>
using namespace std;
int a[200010],b[200010],c[200010];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        int t=a[i]-i;
        if(t>=0) b[i]=t;
        else b[i]=t+n;
        c[b[i]]++;
    }
    int maxn=0;
    for(int i=1;i<n;i++){
        maxn=max(maxn,c[i-1]+c[i]+c[i+1]);
    }
    maxn=max(maxn,c[0]+c[1]+c[n-1]);
    maxn=max(maxn,c[n-1]+c[n-2]+c[0]);
    cout<<maxn;
    return 0;
}

\texttt{addnine} \texttt{Code}

这里用max_element求得最大值。

#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
using ll = long long;
using ld = long double;

int main() {
    int N;
    cin >> N;
    vector<int> p(N), q(N);
    for (int i = 0; i < N; i++) cin >> p[i];
    vector<int> cnt(N, 0);
    for (int i = 0; i < N; i++) {
        int x = (p[i] + N - i) % N;
        cnt[(x-1+N) % N]++;
        cnt[x]++;
        cnt[(x+1) % N]++;
    }
    cout << *max_element(all(cnt)) << endl;
    return 0;
}