题解：P9728 [EC Final 2022] Dining Professors

Thorongil_Gondor · 2024-05-23 15:58:10 · 题解

P9728 [EC Final 2022] Dining Professors 题解

思路

两种情况：

• 可以吃辣，满意度为此教授能吃到的菜的数量，不区分辣菜还是不辣菜。
• 不能吃辣，满意程度为此教授能吃到的不辣的菜的数量，求出最大的满意度。

答案为 n\times3 减去每道菜对满意度影响总值，所以尽量少减不能吃辣人数。

由于圆桌是一个环，故要破环成链。

具体思路见代码注释。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,x,sum;
int a[100005],cnt[100005];
signed main(){
    cin>>n>>x;
    for(int i=1;i<=n;i++)cin>>a[i];
    a[0]=a[n],a[n+1]=a[1];//破环成链
    for(int i=1;i<=n;i++){
        for(int j=i-1;j<=i+1;j++){
            if(!a[j])cnt[i]++;//累加不能吃辣人数 
        }
    }
    sort(cnt+1,cnt+1+n);//排序不能吃辣人数
    for(int i=1;i<=x;i++)sum+=cnt[i];//可吃辣人数 
    cout<<3*n-sum;
    return 0;
}