15pts AC on#1#15#16求调

#include<bits/stdc++.h>
using namespace std;
int t;
struct student{
	int a1,a2,a3;
}a[100005];
struct xx{
	int f,h,c;
}k1[100005],k2[100005],k3[100005];
bool cmp(xx x,xx y)
{
	return x.c>y.c;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		int n,sum1=0,sum2=0,sum3=0,n1=0,n2=0,n3=0;
		memset(k1,0,sizeof(k1));
		memset(k2,0,sizeof(k2));
		memset(k3,0,sizeof(k3));
		memset(a,0,sizeof(a));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d%d",&a[i].a1,&a[i].a2,&a[i].a3);
			if(a[i].a1>a[i].a2)
			{
				if(a[i].a1>a[i].a3)
				{
					n1++;
					sum1+=a[i].a1;
					k1[n1].h=i;
					k1[n1].f=a[i].a1;
					k1[n1].c=max(a[i].a1-a[i].a2,a[i].a1-a[i].a3);
				}
				else
				{
					n3++;
					sum3+=a[i].a3;
					k3[n3].h=i;
					k3[n3].f=a[i].a1;
					k3[n3].c=max(a[i].a3-a[i].a2,a[i].a3-a[i].a1);
				}
			}
			else
			{
				if(a[i].a2>a[i].a3)
				{
					n2++;
					sum2+=a[i].a2;
					k2[n2].h=i;
					k2[n2].f=a[i].a2;
					k2[n2].c=max(a[i].a2-a[i].a1,a[i].a2-a[i].a3);
				}
				else
				{
					n3++;
					sum3+=a[i].a3;
					k3[n3].h=i;
					k3[n3].f=a[i].a3;
					k1[n3].c=max(a[i].a3-a[i].a2,a[i].a3-a[i].a1);
				}
			}
		}
		sort(k1+1,k1+1+n1,cmp);
		sort(k2+1,k2+1+n2,cmp);
		sort(k3+1,k3+1+n3,cmp);
		if(n1>0.5*n)
		{
			while(n1>0.5*n)
			{
				if(a[k1[n1].h].a2>a[k1[n1].h].a3)
				{
					n2++;
					sum2+=a[k1[n1].h].a2;
					k2[n2].h=k1[n1].h;
					k2[n2].f=a[k1[n1].h].a2;
				}
				else
				{
					n3++;
					sum3+=a[k1[n1].h].a3;
					k2[n3].h=k1[n1].h;
					k2[n3].f=a[k1[n1].h].a3;
				}
				sum1-=k1[n1].f;
				n1--;
			}
		}
		else if(n2>0.5*n)
		{
			while(n2>0.5*n)
			{
				if(a[k2[n2].h].a1>a[k2[n2].h].a3)
				{
					n1++;
					sum1+=a[k2[n2].h].a1;
					k1[n1].h=k2[n2].h;
					k1[n1].f=a[k2[n2].h].a1;
				}
				else
				{
					n3++;
					sum3+=a[k2[n2].h].a3;
					k3[n3].h=k2[n2].h;
					k3[n3].f=a[k2[n2].h].a3;
				}
				sum2-=k2[n2].f;
				n2--;
			}
		}
		else if(n3>0.5*n)
		{
			while(n3>0.5*n)
			{
				if(a[k3[n3].h].a2>a[k3[n3].h].a1)
				{
					n2++;
					sum2+=a[k3[n3].h].a2;
					k2[n2].h=k3[n3].h;
					k2[n2].f=a[k3[n3].h].a2;
				}
				else
				{
					n1++;
					sum1+=a[k3[n3].h].a1;
					k1[n3].h=k3[n3].h;
					k1[n3].f=a[k3[n3].h].a1;
				}
				sum3-=k3[n3].f;
				n3--;
			}
		}
		cout<<sum1+sum2+sum3<<endl;
	}
	return 0;
}