AtCoder ABC286 C - Chinese Restaurant

题目描述

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

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

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

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

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

样例输入输出

4
1 2 0 3

数据范围

\(3 \le N \le 2 \times 10^5\)

\(0 \le p_i < N\)

思路

如果枚举所有的桌子的状态，那么将会是 \(\Theta(N)\) 的复杂度，显然不可取。

如果我们将思维颠倒过来，从每个人的角度思考，这样显然简单很多。

定义 \(cnt_i\) 表示如果桌子旋转 \(i\) 次时的高兴人数，那么只需要统计 \(cnt\) 的最大值即可。

对于每一个人 \(p_i\)，只要旋转了 \((i-1)\bmod N\)、 \(i\) 或 \((i+1)\bmod N\) 次后，就会让这个人高兴。因此枚举每一个人 \(p_i\)，并将可以使它高兴的旋转次数自增 \(1\)，最终求最大值即可。

代码

#include <iostream>
#include <unordered_map> 

using namespace std;

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int n, p[N], mx = -inf;

// 哈希表 
unordered_map<int, int> cnt;

// x 转到 y 的旋转次数 
int f(int x, int y){
	if(x == y){
		return 0;
	}
	if(x < y){
		return y - x;
	}
	return n - x + y;
}

signed main(){
	scanf("%lld", &n);
	
	for(int i=0; i<n; i++){
		scanf("%lld", p+i);
		// 将每种会使 p[i] 高兴的旋转次数全部加 1 
		cnt[f((p[i] - 1) % n, i)]++;
		cnt[f(p[i] % n, i)]++;
		cnt[f((p[i] + 1) % n, i)]++;
	}
	
	// 寻找最大值 
	for(auto e : cnt){
		mx = max(mx, e.second);
	}
	
	printf("%lld", mx);
	
	return 0;
}