我在考场上取得了100分的好成绩，你也来试试吧。

题目分析

我不懂什么反悔贪心，这个，那个算法的，甚至我连20分的大暴力和70分$O(n^2)$(我真不会，所以我连从低分到高分的解法一步步推理都讲不了)，排序就能做对

显然，这三个值中有一个没用。(证明呢？)

我们来像一个极限情况，所有人的最满意，次最满意，最不满意的部门都是一样的，分别为$1,2,3$，那很显然，我们把 $\frac{n}{2}$ 的人放到部门1，$\frac{n}{2}$ 的人放到部门2，然后我们发现，所有人都最不满意的社团居然没有人！！

这是为什么呢？
其实是基于一个分配的性质："不存在一个部门被分配多于 $\frac{n}{2}$​ 个新成员"
一个$n$的限制：其中 $n$ 为偶数
我们就可以得出结论：所有人无论满意如何，都可以保证只用两个部门装下所有人，则所有人无论如何分配，多可以使每个人都不会被分到自己三个部门中最不满意的部门。这条结论保证了接下来贪心方法的成立，是做对这道题的核心思想 (至少我做出这道题想到这之后贪心瞎蒙都蒙对了)

贪心设计

因为排除了最小值，我们就只用对剩下的最大值和次大值分析，这时我们想一下贪心的核心思想：只要贪不死，就往死里贪。

对于这$n$个人，我们肯定希望所有人多去自己最满意的部门，但是在我上面的极端情况下，必会有$\frac{n}{2}$个人被分到次最满意的部门，这时我们不妨设一个值$x$为一个人被分到最满意部门与次最满意的部门的满意度差值，则$x$同时也代表一个人不被分到最满意部门的满意度的损失值，那这有什么用呢？

因为我们想把所有的人都放到其最满意的部门，那当一个人不得不被放到次最满意部门的时候，我们的总满意度就会减少$x$，这就是为什么$x$是一个损失值。

由此我们的贪心就显而易见了：把损失值降到最低！
但是如何把损失值降到最低呢？

排序设计

我们在决定把一个人放到哪个部门时，越靠后决定的人越不会被分到自己最满意的部门，这时就越可能造成损失，所以我们就是要让越可能做成损失的的人能够造成的损失越小,显然，我们按上述差值$x$从大到小排序再顺次分配部门即可。

Code

#include<bits/stdc++.h>
using namespace std;
int t,n,ji[4];
long long sum;
struct student{
	int b1,b2;
	long long t1,t2;
}a[100005];
struct manyi{
	int num;
	long long s;
}m[4];
bool cmp(manyi x,manyi y){
	return x.s>y.s;
}
bool cmp1(student x1,student x2){  //差值排序
	return (x1.t1-x1.t2)>(x2.t1-x2.t2);
}
int main()
{
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);sum=0;
		memset(ji,0,sizeof(ji));  //多测必清空
		for(int i=1;i<=n;i++){  
			scanf("%lld %lld %lld",&m[1].s,&m[2].s,&m[3].s);
			m[1].num=1;m[2].num=2;m[3].num=3;  //收集三个满意度和对应部门，排除最小值
			sort(m+1,m+4,cmp);
			a[i].t1=m[1].s;a[i].b1=m[1].num;
			a[i].t2=m[2].s;a[i].b2=m[2].num;
		}
		sort(a+1,a+1+n,cmp1);
		for(int i=1;i<=n;i++){
			if(ji[a[i].b1]<(n>>1)){  //若一个人能被分到最满意部门，直接分配即可
				sum+=a[i].t1;ji[a[i].b1]++;
			}
			else{  //若不能被分到最满意部门，只能接受损失
				sum+=a[i].t2;ji[a[i].b2]++;
			}
		}  //不要忘了将人对应分配到的部门人数增加
		printf("%lld\n",sum);
	}
	return 0;
}