CF1825C LuoTianyi and the Show

Rhodes Island / 2023-05-09 / 原文

传送门(luogu)

传送门(CF)

前言

~~我来水题解力~~

简化题意

$n$ 个人，$m$ 个座位，每个人落座的方法有三种：

坐最左边的人的左边，没人的话就做 $m$ 号座位，若最左边的为 $1$ 号，就离开；
坐最右边的人的右边，没人的话就做 $1$ 号座位，若最右边的为 $m$ 号，就离开；
坐在 $x_i$ 号座位上，有人就离开。

问任意搭配 $n$ 个人落座顺序，坐下人数的最大值。

~~（这真的是简化题意吗）~~

Solution

思路

容易发现我们可以：

一直放 $1$ 或 $2$ 类人，碰到 $3$ 类人要坐的位置就让 $3$ 类人坐。

因为碰到第 $3$ 类人的座位时，与其放 $1$ 或 $2$ 类人浪费放置次数，不如直接放第 $3$ 类人。

那么我们要从哪儿开始放才能保证是最优解呢？

不难发现，起点的位置要么是一个第 $3$ 类人的左右两边，要么是 $1$ 或 $m$ 号点。

于是，对于每一个 $3$ 类人，我们可以计算出他左右两边不计其他第 $3$ 类人占的座位的空座位数，以此来一一放置第 $1,2$ 类人。

别忘了 $1,m$ 号点也是起点。

时间复杂度

计算空座位只需 $O(n)$。

代码实现

写的丑，轻喷。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5 + 5;

int t, n, m;
int a[N], cntl, cntr;

int main(){
	cin >> t;
	while(t -- ) {
		cntr = 0; cntl = 0; //多次不清空，亲人两行泪
		
		cin >> n >> m; 		
		for (int i = 1; i <= n; ++ i ) 
			cin >> a[i];
		
		sort(a + 1, a + 1 + n); //排序方便计算空座位数
		
		int i;
		for (i = 1; i <= n; ++ i ) //计算 1,2 类人的数量 
			if(a[i] == -1) cntl ++ ;
			else if(a[i] == -2) cntr ++ ;
			else break;
		
		n = unique(a + i, a + 1 + n) - a - 1;  
		//将第 3 类人去重，因为相同座位只能坐一个；i 是第一个第 3 类人的编号
		
		int ans = 0;
		
		for (int j = i; j <= n; ++ j ) {
			int L = a[j] - 1 - (j - i); //(j-i) -> a[j]之前有多少个第 3 类人
			int R = m - a[j] - (n - j); //(n-j) -> a[j]之后有多少个第 3 类人
			ans = max(ans, 1 + n - i + min(L, cntl) + min(R, cntr));
		} 
		
		ans = max(ans, n - i + 1 + max(min(cntl, m - (n - i + 1)), min(cntr, m - (n - i + 1))));
		//(n - i + 1) -> 第 3 类人个数
		
		cout << ans << "\n";
	}
	return 0;
}