自动搬运

查看原文

来自洛谷，原作者为

	Star_Universe 狂减发犇 | INFP-T | 称呼 SU | 代词使用他 | 愿此行，终抵群星 | 处女作 /article/wep12twg | 互关看心情，如果不想关注会用两小号回关，私信！

搬运于2025-08-24 22:51:13，当前版本为作者最后更新于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;
}

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