T1社团招新(club)
原题链接
T1出这个...
以下规定三个社团分别为 \(a,b,c\)。
第一眼的思路尝试对每个人对三个社团的满意度取 \(max\)，然后依次选最优的，很快发现这么做不行，因为有可能在满足限制后其他人能带来的贡献极小。
这时发现也许需要撤销操作或者说反悔，我就开始想如果满足限制后用接下来的人尝试替换，细想了一下其实有点麻烦而且不能保证直接交换就是最优的，很没前途就弃掉了，后来的思路都比较凌乱。
重新复盘一下题目的条件，我们发现满足 \(\frac{n}{2}\) 限制的社团最多存在一个，那么一个人的参加社团的最优策略一定会在最大值或者次大值之中取到，这是一个非常好的性质，如果一个人的报名策略需要撤销，那么直接选到次大值就好了，也就是对答案减去最大值与次大值之差。我们希望答案减去的值尽可能的少，选择维护对每个人最大值与次大值的差维护小根堆，因为有三个社团，所以开三个，最终哪个社团超出限制就从哪个社团调整，直到满足限制。
在这题上浪费时间有点多了，只是换思路想题还是不够的，每隔一段时间要对题中有启发的信息做整理，麻烦的性质果断摘掉。
#define int long long
const int N=1e5+5;
int T;
int n,m;
struct node{int x,y,z;int mx;
}a[N];
bool cmp(node i,node j){return i.mx>j.mx;
}
priority_queue<int> q1,q2,q3;
int cnta,cntb,cntc;
int ans;
void clear(){ans=cnta=cntb=cntc=0;while(!q1.empty()) q1.pop();while(!q2.empty()) q2.pop();while(!q3.empty()) q3.pop();
}
void xpigeon(){cin>>n;m=n/2;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y>>a[i].z;a[i].mx=max({a[i].x,a[i].y,a[i].z});}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){if(a[i].x==a[i].mx){cnta++;q1.push(max(a[i].y,a[i].z)-a[i].mx);}else if(a[i].y==a[i].mx){cntb++;q2.push(max(a[i].x,a[i].z)-a[i].mx);}else if(a[i].z==a[i].mx){cntc++;q3.push(max(a[i].y,a[i].x)-a[i].mx);}ans+=a[i].mx;}if(cnta>m){int k=cnta-m;while(k--){ans+=q1.top();q1.pop();}}else if(cntb>m){int k=cntb-m;while(k--){ans+=q2.top();q2.pop();}}else if(cntc>m){int k=cntc-m;while(k--){ans+=q3.top();q3.pop();}}cout<<ans<<'\n';clear();
}