Question

一道pascal的题目，叫做选派选手，请各位大虾帮忙理出程序，最好有简单注释。谢谢！

选派选手
(ekipa.pas/c/cpp)
【问题描述】

在银河系深处正要举行一场编程比赛，你的任务就是选出参赛选手。
有N个学生申请参加比赛，比赛共有M个项目，每个人都懂得一些各个项目的知识。我们把学生的知识水平用一些实数表示。你最多可以选出K名学生参赛，但没有一个人能同时参加几项比赛。一项比赛可以有多人参加。
给出每个学生的每项知识水平，从中选出参赛选手和他们所参加的项目，使知识水平之和最大。

【输入格式】

第1行包括3个整数N，M和K(1≤M≤100,1≤K≤N≤100)。
接下来的M行是每个人每个项目的知识水平。每一行有N个数对(i,s)，i表示学生编号，正实数s表示他们对应项目的知识水平。其中(0≤s≤10)，这N个数对是按知识水平的降序排列的。学生的编号从一到N。每一行中，每个学生的编号只会出现一次。

【输出格式】

仅一行，输出选出学生知识水平的最大值，保留一位小数。

【输入输出样例】

ekipa.in ekipa.out
3 2 2
2 3.0 1 0.2 3 0.1
3 1.0 2 0.5 1 0.2
4.0
〖样例1解释〗
有两个项目，第一个项目水平最高的学生是第二位，知识水平为3.0；其次是1号学生，知识水平为0.2，然后是知识水平为0.1的3号学生。
很明显，最优解是分别将2号和3号学生派去参加第一和第二个项目。

ekipa.in ekipa.out
4 4 3
4 5.0 2 4.0 3 2.0 1 1.0
2 2.0 3 1.0 1 0.5 4 0.3
4 6.0 3 5.0 2 2.0 1 0.0
1 4.0 2 3.0 4 0.6 3 0.3
15.0

Answer 1

【问题分析】
这题很明显是用贪心做。
题目中说“没有一个人能同时参加几项比赛，一项比赛可以有多人参加”，而输入数据是M行，表示M个比赛项目，每行有N个人的该项的知识水平，那么就可以开一个二维数组A，I表示第I个人，A[I, J]存放第I个人的知识水平（J无实际意义，因为A[I, J]没有顺序）。这样就将以项目为单位转化为以人为单位，只需要找出每个人的最大水平，放入数组T，按降序排序后，取T数组的前K项的和，即为知识水平最大值。
【参考程序】
Program Ekipa_Tzefz_Tzy;
Const
Fn = 'ekipa';
Var
N, M, K: Longint;
J1, J2 : Longint;//循环变量
I, J : Longint;//I用到了2次，第1次作数对(S,I)，第2次作循环变量；J为循环变量
S, Max : Real;//S作数对(S,I)；Max为每个人在所有项目中的最大水平
Ans : Real;//Ans为输出数据
A : Array[1.. 100, 0.. 100] Of Real;//A数组用法见【问题分析】
T : Array[0.. 100] Of Real;//T数组用法见【问题分析】
Begin
Assign(Input, Fn + '.in'); Reset(Input);
Assign(Output, Fn + '.out'); Rewrite(Output);
Readln(N, M, K);
For J1:= 1 To M Do
For J2:= 1 To N Do
Begin
Read(I, S);
A[I, J1]:= S;//读入后存放第I个人的各项水平
End;
For J1:= 1 To N Do
Begin
Max:= 0;
For J2:= 1 To M Do
If A[J1, J2] > Max Then Max:= A[J1, J2];
T[J1]:= Max;
End;//找出每个人在各项中的最大水平，存放入T数组
For I:= 1 To N - 1 Do
For J:= I + 1 To N Do
If T[I] < T[J] Then
Begin
T[0]:= T[I];
T[I]:= T[J];
T[J]:= T[0];
End;//对T数组进行降序排序
Ans:= 0;
For I:= 1 To K Do
Ans:= Ans + T[I];//取T数组前K项的和，即K个参赛的人水平和
Writeln(Ans: 0: 1);//输出，保留一位小数
Close(Input);
Close(Output);
End.
【考查知识点】
贪心。

还有不懂可以百度Hi我

Answer 2

给个思路吧啊 贪心法解这道题
将所有的知识水平数据从大到小排序 ，然后从头扫一遍 遇见能够参加比赛的选手就把他设置成不能再参加比赛 然后加上他在这一项目中的知识水平（由于数组是从大到小排序的 而且一个项目可以有多个人参加 所以这种做法是正确的）
用第二组输入输出举例 排完序 之后是 6.0 5.0 5.0 4.0 4.0 ……………… 首先+6.0 然后4号再不能用了 然后判断5.0 的数据 ，假设第一个5.0 是4 号的， 那么它不能再用 看下一个 也是5.0 不过是3号 于是+5.0 设置3号不能用 然后 再 +4.0 设置2号不能用 一直到选出了k个人为止

不知道我这么说你能不能明白 望采纳…………

Answer 3

Var
N, M, K:Longint;
J1, J2:Longint;
I, J:Longint;
S, Max:Real;
Ans:Real;
A:Array[1.. 100, 0.. 100] Of Real;
T:Array[0.. 100] Of Real;
Begin
Readln(N, M, K);
For J1:= 1 To M Do
For J2:= 1 To N Do
Begin
Read(I, S);
A[I, J1]:= S;
End;
For J1:= 1 To N Do
Begin
Max:= 0;
For J2:= 1 To M Do
If A[J1, J2] > Max Then Max:= A[J1, J2];
T[J1]:= Max;
End;
For I:= 1 To N - 1 Do
For J:= I + 1 To N Do
If T[I] < T[J] Then
Begin
T[0]:= T[I];
T[I]:= T[J];
T[J]:= T[0];
End;
Ans:= 0;
For I:= 1 To K Do
Ans:= Ans + T[I];
Writeln(Ans: 0: 1);
End