专栏文章

P14361 [CSP-S 2025] 社团招新/club 个人题解

kkxkk665
P14361题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mind6moa
此快照首次捕获于
2025/12/02 00:29
3 个月前
此快照最后确认于
2025/12/02 00:29
3 个月前
查看原文

前言

本人是蒟蒻，考场胡思乱想2.5h2.5h才想出来的，这也是本人CSP-S第一个考场上做出来的题，为此记录一下。

思路过程

考场上想了很多思路，例如什么dpdp啊，记搜啊之类的，但是发现都不太行，并且本人不怎么会dpdp，于是根本没想过dpdp咋写，只会贪心走到底，想太长时间做不出来了就考虑先打特殊性质。

特殊性质 AA

一眼秒，按a1a_1从大到小排序取前n/2n/2个即可。

特殊性质 BB

这个就有难度了。
一开始肯定是先让他们贪心地选自己最爱的社团，顺便统计每个社团有多少人，选完后如果没有社团超过n/2n/2那就不用再调了，那如果有呢？
可以发现移走对该社团满意度较小的人不一定是最优的，所以移人的根据并不是满意度的大小，那是什么呢？
我们hardly注意到移走时满意度会减小，于是我们便可以聚焦于减少的满意度，此时就可以发现不断移走减少量最少的人直至人数符合要求时，满意度的减少量肯定最少，所以此时最后满意度总和肯定是最大的。
根据这个思路，先算出这个社团里面的人移走时减少的满意度，再对减少量进行排序，让减少量少的人移到另一个社团直至人数满足要求，最后统计每个人选的社团的满意度总和即可。

正解

在特殊性质BB发现了做法后，考虑把它推广到三个社团的情况。
这时就可以发现做法并没有什么改变，只不过要额外记录一下每个人第一喜欢的社团和第二喜欢的社团的分别是哪个以及其满意度，移人时注意把那个人移到他第二喜欢的社团而不是随便乱移的即可。

时间复杂度

时间复杂度主要花费在sortsort上，故为O(nlogn)O(nlogn)。

代码

以下为考场代码。
若觉得本人代码风格不好请轻喷orz
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t,n;
int cs[100005];
struct node
{
    int d[5];
}a[100005];
struct nod
{
    int x,y;
};
bool cmp3(nod a,nod b)
{
    return a.y>b.y;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    freopen("club.in","r",stdin);
    freopen("club.out","w",stdout);
	cin >> t;
	while(t)
	{
		t--;
		cin >> n;
		int k1=0,k2=0;
		for(int i=1;i<=n;i++) cin >> a[i].d[1] >> a[i].d[2] >> a[i].d[3];
        int f=0,s=0,h=0;
        for(int i=1;i<=n;i++)//first choose
        {
            int mx=max(max(a[i].d[1],a[i].d[2]),a[i].d[3]);
            if(mx==a[i].d[1])
            {
                cs[i]=1;
                f++;
            }
            else if(mx==a[i].d[2])
            {
                cs[i]=2;
                s++;
            }
            else if(mx==a[i].d[3])
            {
                cs[i]=3;
                h++;
            }
        }
        if( (f<=n/2 and s<=n/2) and h<=n/2 ) int u;//no fight
        else
        {
            int k;
            if(f>n/2) k=1;
            else if(s>n/2) k=2;
            else if(h>n/2) k=3;
            vector<nod> lt;
            int nx1=k%3+1,nx2=nx1%3+1;
            for(int i=1;i<=n;i++)
            {
                if(cs[i]!=k) continue;
                lt.push_back( {i,min(a[i].d[k]-a[i].d[nx1],a[i].d[k]-a[i].d[nx2])} );
            }
            sort(lt.begin(),lt.end(),cmp3);
            for(int i=0;i<lt.size();i++)
            {
                if(i<=n/2-1) continue;
                if(a[lt[i].x].d[nx1]>a[lt[i].x].d[nx2]) cs[lt[i].x]=nx1;
                else cs[lt[i].x]=nx2;
            }
        }
        ll sum=0;
        for(int i=1;i<=n;i++) sum+=a[i].d[cs[i]];
        cout << sum << endl;
    }
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...