P9728 [EC Final 2022] Dining Professors 题解

_Star_Universe_ · 2024-08-07 21:09:41 · 题解

题目传送门

看完了其他题解，总算学会了这道题，也来发一篇题解吧。

思路

算法：贪心。首先第 i 位教授只能吃到面前的菜与相邻的两盘菜，即第 i 盘菜、第 (i \bmod n)+1 盘菜和第 ((i+n-2) \bmod n)+1 盘菜。对于能吃辣的教授来说，满意度一定为 3；对于不能吃辣的教授来说满意度为能吃到的不辣的菜的数量。

最好的情况就是所有人都能吃辣，即最大满意度为 3 \times n。我们可以用数组统计不能吃辣的人数并升序排列，然后圆桌的前 a 个位置放辣的菜，后 n-a 个位置放不辣的菜，易证这样是最优策略。定义一个变量 ans ，从第 1 个位置遍历到第 a 个位置，每次将 ans 加 1，最后输出 3 \times n-ans 即可。

从这篇题解里学到了由于圆桌是一个环，要有这么一句代码：

i[0]=i[n];i[n+1]=i[1];

代码

#include<bits/stdc++.h>
using namespace std;

int n,a,ans,i[100005],z[100005];
signed main(){
    cin>>n>>a;
    for(int k=1;k<=n;k++){
        cin>>i[k];
    }
    i[0]=i[n];i[n+1]=i[1];
    for(int k=1;k<=n;k++){
        for(int j=k-1;j<=k+1;j++){
            if(i[j]!=1){
                z[k]++;
            }
        }
    }
    sort(z+1,z+n+1);
    for(int k=1;k<=a;k++){
        ans+=z[k];
    }
    cout<<3*n-ans;
    return 0;
}

因为本蒟蒻是跟着其他题解学习的，可能有部分内容相似，如有侵权立即撤下。