（补题）小塔的饭

题目描述

小塔是一位热爱美食的算法研究员，她正在研究如何为朋友们安排美食派对以获得最大的幸福感。她邀请了N位朋友来品尝M种不同的食物，并记录了每位朋友对每种食物的好感度ai,j 。

现在，小塔想要设计一个美食分配方案，使得总好感度最高，同时保证至少有一种食物被超过一半的朋友品尝过。你能帮助她解决这个问题吗？

给定N个人和M种食物，每个人对每种食物有一个好感度ai,j 。你需要找到一个分配方案，使得：

• A. 每个人恰好选择一种食物
• B. 至少有一种食物被超过⌊N/2⌋个人选择
• C. 所有选择的总好感度最大

输入

输入包含多组测试数据。第一行包含一个整数T，表示测试数据的组数。

对于每组测试数据：

第一行包含两个整数N和M，表示人数和食物种类数
接下来N行，每行包含M个整数ai,1,ai,2,...,ai,M ，表示第i个人对第j种食物的好感度
数据范围：
1≤T≤10
1≤n≤100
1≤m≤1000
1≤ai,j≤109

输出

对于每组测试数据，输出一个整数，表示满足条件的最大总好感度。

样例输入

2
5 3
1 2 3
4 5 6
7 8 9
10 11 12
13 14 15
3 2
200 100
400 300
500 600

样例输出

45
1200

贪心解法（O(nmlogn)）：最小损失替换，直接满足约束

• 枚举 “热门食物”：同样假设最终被超过半数人选择的食物是 x（遍历所有食物）。
• 计算 “损失”：如果一个人选 x 而非他原本最喜欢的食物，好感度会减少多少（loss[i] = 原最高好感 - a[i][x]）。
• 最小化损失：为了让 x 被至少 ⌊N/2⌋+1 人选择，需要选损失最小的 ⌊N/2⌋+1 个人来 “替换”（选 x），这样总损失最小，总好感度最大。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n,m;
ll a[109][1009];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		ll total=0,like[109]{0},ans=0;
		for(int i=0;i<n;++i){
			for(int j=0;j<m;++j){
				scanf("%lld",&a[i][j]);
				like[i]=max(like[i],a[i][j]);
			}
			total+=like[i];
		}
		ll loss[109]{0};
		for(int i=0;i<m;++i){
			for(int j=0;j<n;++j){
				loss[j]=like[j]-a[j][i];
			}
			sort(loss,loss+n);
		    ll bug=0;
		    for(int j=0;j<n/2+1;++j){
			    bug+=loss[j];
		    }
		    ans=max(ans,total-bug);
		}
		printf("%lld\n",ans);
	}
	return 0;
}