2.18号英语翻译
题目来源:https://acs.jxnu.edu.cn/problem/HDU1031
重点词汇:
poll:n.投票,选举人民意;v.投票;
graph:n.图形,图表;v.图解;
adjacent:adj.相邻的;
indices:n.指数;
Design T-Shirt
1000ms 0K
描述:
Soon after he decided to design a T-shirt for our Algorithm Board on Free-City BBS, XKA found that he was trapped by all kinds of suggestions from everyone on the board. It is indeed a mission-impossible to have everybody perfectly satisfied. So he took a poll to collect people's opinions. Here are what he obtained: N people voted for M design elements (such as the ACM-ICPC logo, big names in computer science, well-known graphs, etc.). Everyone assigned each element a number of satisfaction. However, XKA can only put K (<=M) elements into his design. He needs you to pick for him the K elements such that the total number of satisfaction is maximized. 在他决定在自由城论坛上为我们的算法板设计一件 T 恤后不久,XKA 发现他被板上每个人的各种建议所困。让每个人都完全满意确实是一项不可能完成的任务。于是,他进行了一次民意调查,收集人们的意见。以下是他获得的结果: N 人投票给了 M 设计元素(如 ACM-ICPC 标志、计算机科学界的大人物、知名图等)。每个人都为每个元素分配了一个满意的数字。但是,XKA 只能将 K (<=M) 个元素放入他的设计中。他需要你为他挑选 K 个元素,以使满足的总数最大化。输入:
The input consists of multiple test cases. For each case, the first line contains three positive integers N, M and K where N is the number of people, M is the number of design elements, and K is the number of elements XKA will put into his design. Then N lines follow, each contains M numbers. The j-th number in the i-th line represents the i-th person's satisfaction on the j-th element. 输入由多个测试用例组成。对于每种情况,第一行包含三个正整数 N、M 和 K,其中 N 是人数,M 是设计元素的数量,K 是 XKA 将放入他的设计中的元素数量。然后是 N 行,每行包含 M 个数字。第 i 行中的第 j 个数字表示第 i 个人对第 j 个元素的满意度。输出:
For each test case, print in one line the indices of the K elements you would suggest XKA to take into consideration so that the total number of satisfaction is maximized. If there are more than one solutions, you must output the one with minimal indices. The indices start from 1 and must be printed in non-increasing order. There must be exactly one space between two adjacent indices, and no extra space at the end of the line. 对于每个测试用例,在一行中打印您建议 XKA 考虑的 K 个元素的索引,以便最大化满意度的总数。如果有多个解决方案,则必须输出具有最小索引的解决方案。索引从 1 开始,并且必须以非递增顺序打印。两个相邻索引之间必须恰好有一个空格,并且行尾没有多余的空格。样例输入:
3 6 4 2 2.5 5 1 3 4 5 1 3.5 2 2 2 1 1 1 1 1 10 3 3 2 1 2 3 2 3 1 3 1 2
样例输出:
6 5 3 1 2 1