CF1824A/1825C题解

$\color{white}{\text{蒟蒻第一篇题解}}$

我们可以先定义：

1. 一类人从左边进，挨着遇到的第一个人坐下。
2. 二类人从右边进，挨着遇到的第一个人坐下。
3. 三类人坐在第 $k$ 个座位上，如果那个座位有人了，离开。

很明显，有以下几个结论：

• 只要三类人人数不大于 $m$，就能把他们全安排下。
• 如果第一个入座的人是一类人，那二类人就可以退票了(第 $m$ 个座位被占了)，反之亦然。

所以我们可以先让一个三类人入座，把所有座位分为两部分，左边在让所有三类人入座的基础上再让一类人入座，右边在让所有三类人入座的基础上再让二类人入座。枚举这个把所有座位分成两部分的特殊三类人即可。

当然还得特判以下两种情况：

1. 只坐一、三类人。不坐二类人。
2. 只坐二、三类人。不坐一类人。

理论存在，代码如下：

#include<cstring>
#include<iostream>
using namespace std;
int t,n,m,way1,way2,cnt,ans;
int way3[100002],ji[100002],s[100002];
int main(){
	cin>>t;
	while(t--){
		cnt=0;//三类人数
		ans=0;
		way1=way2=0;//一、二类人数
		memset(ji,0,sizeof(ji));
		memset(s,0,sizeof(s));
		cin>>n>>m;
		for(int i=1;i<=n;++i){
			int k;
			cin>>k;
			switch(k){
				case -1:
					++way1;
					break;
				case -2:
					++way2;
					break;
				default:
					if(!ji[k]){//去重，如果重复那也只能坐一个人
						ji[k]=1;//有点类似计数排序
						++cnt;
					}
			}
		}
		for(int i=1;i<=m;++i){//前缀和
			s[i]=s[i-1]+ji[i];
		}
		ans=min(max(way1,way2)+cnt,m);//特判
		for(int i=1;i<=m;++i){
			if(ji[i]){
				ans=max(ans,cnt+min(i-1-s[i-1]/*编号小于i的空座数量，可以让一类人入座*/,way1)+min(m-i-(s[m]-s[i])/*编号小于i的空座数量，可以让二类人入座*/,way2));
			}
		}
		cout<<ans<<endl;
	}
}