[CSP-S 2025] 社团招新 / club

前言

我是不是赢在这个题

1

分钟秒了？~~这是不是矛盾的病句。~~

题目分析

首先默认全选满意度最大的社团，如果合法肯定就是答案，这一定最优。

考虑不合法，对人最多的社团移走一些人即可。由于要移到

\frac{n}{2}

人为止一定最优，不需要考虑因此其他集合元素超出限制的情况。可以预处理每个人到她次喜欢的社团的满意度差。直接排序贪心选最小的即可。

时间复杂度

O(n\log n)

，好像可以用桶做到

O(n)

。

代码

CPP

#include<bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
using namespace std;
constexpr int N=1e5+1;
int T,n,a[N][4],maxv,ans;
vector<int>members[4];
void Main(){
	for(int i=1;i<=3;i++)
		members[i].clear();
	ans=0;
	cin>>n;
	for(int i=1,x,y;i<=n;i++){
		cin>>a[i][1]>>a[i][2]>>a[i][3];
		if(a[i][1]>=a[i][2]&&a[i][1]>=a[i][3]){
			x=1,
			y=(a[i][2]>a[i][3]?2:3);
		}
		else if(a[i][2]>=a[i][1]&&a[i][2]>=a[i][3]){
			x=2,
			y=(a[i][1]>a[i][3]?1:3);
		}
		else{
			x=3,
			y=(a[i][1]>a[i][2]?1:2);
		}
		members[x].push_back(a[i][x]-a[i][y]);
		ans+=a[i][x];
	}
	if((maxv=max({members[1].size(),members[2].size(),members[3].size()}))<=n/2)
		cout<<ans<<'\n';
	else{
		int x=(members[1].size()==maxv?1:(members[2].size()==maxv?2:3)),rem=members[x].size()-(n/2);
		sort(ALL(members[x]));
		for(int i=0;i<rem;i++)
			ans-=members[x][i];
		cout<<ans<<'\n';
	}
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr),cout.tie(nullptr);
	for(cin>>T;T;--T)
		Main();
	return 0;
}

[CSP-S 2025] 社团招新 / club

文章操作

前言

题目分析

代码

相关推荐

评论

[CSP-S 2025] 社团招新 / club