B. Going to the Cinema

https://codeforces.com/contest/1782/problem/B

题目大意就是给定n个人，每个人有一个除自己之外的最少陪同人数，选一部分人去电影院，要求去的人人数大于等于去的每个人要陪同的人数，不去的人要求陪同的人数要大于要求去的人数

废话不多说上代码

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=2e5+10;

int a[N],p[N];

int t;

int main(){

	 cin>>t;

	 while(t--){

	 	int n;

	 	cin>>n;

	 	int m=0;

	 	memset(p,0,sizeof p);

	 	for(int i=1;i<=n;i++){

	 		int x;

	 		cin>>x;

	 		if(p[x]==0) a[++m]=x;//记录每种陪同人数

	 		p[x]++;//记录每种陪同人数的个数

		 }

	 	sort(a+1,a+1+m);

	 	//我们这里先排序，当序列由小到大时，我们发现如果后面的能去的话，前面的必须得去

	 	int res=0,num=0;

	 	//注意人数减一是因为不包含自己

	 	for(int i=1;i<=m;i++){

	 		if(num<a[i]&&max(num-1,0)>=a[i-1]) res++;//对于方案来说，如果该人不去是合法的则方案数加一

	 		num+=p[a[i]];

	}

	if(num-1>=a[m]) res++;//最后判断一下是否所有人去都合法

	cout<<res<<endl;

	 }

}

巴特西

B. Going to the Cinema

最新文章

热门文章