HDUOJ----(1031)Design T-Shirt

Design T-Shirt

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4370    Accepted Submission(s): 2124

Problem Description

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.

Input

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.

Output

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.

Sample Input

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

Sample Output

6 5 3 1

2 1

Author

CHEN, Yue

Source

CYJJ's Funny Contest #1, Killing in Seconds

Recommend

几次排序就可以ac掉...没啥技术...水体

代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<climits>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 #include<vector>
 8 using namespace std;
 9 
10 typedef struct Nod
11 {
12     int num;
13     float value;
14 }nod;
15   /*二级排序*/
16 int cmp(nod a,nod b)
17 {
18     if(a.value==b.value)
19     {
20         return a.num<b.num;  //小到大
21     }
22     else
23         return a.value>b.value;  //降序大到小
24 }
25 
26 int Less(int a,int b)
27 {
28     return a>b; //降序大到小
29 }
30 int main()
31 {
32     int n,m,k,i;
33     float cnt;
34     while(scanf("%d %d %d",&n,&m,&k)!=EOF)
35     {
36       vector<nod>start(m);
37       vector<int>ans(k);
38       /*初始化*/
39       for(i=0;i<m;i++)
40       {
41           scanf("%f",&start[i].value);
42           start[i].num=i+1;
43       }
44       n--;
45       while(n--)
46       {
47        for(i=0;i<m;i++)
48        {
49           scanf("%f",&cnt);
50           start[i].value+=cnt;
51        }
52       }
53       sort(start.begin(),start.end(),cmp);
54       for(i=0;i<k;i++)
55       {
56         ans[i]=start[i].num;
57       }
58       sort(ans.begin(),ans.end(),Less);
59       printf("%d",ans[0]);
60       for(i=1;i<k;i++)
61       {
62       printf(" %d",ans[i]);
63       }
64       putchar(10);
65     }
66     return 0;
67 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

专题练习---(数论)莫比乌斯反演

            GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32...

373110
来自专栏ml

HDUOJ----1301 Jungle Roads

Jungle Roads Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768...

32570
来自专栏ml

HDUOJ-----2399GPA

GPA Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

36440
来自专栏WindCoder

Declarative Programming: Is It A Real Thing?

由于合作方希望能以英文形式发布,故以后top的译文看时间而定,没时间就不再尝试翻译(而且本来水平也不咋地),仅保留原文于此。本次是一篇关于声明式编程的讨论文章,...

9910
来自专栏ml

HDUOJ---hello Kiki

Hello Kiki Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K...

28490
来自专栏c#开发者

Developing a Transactional Biztalk adapter

Contents Developing a Transactional BizTalk Adapter Using the Microsoft Base Ada...

332130
来自专栏算法修养

ZOJ 80ers' Memory

80ers' Memory ---- Time Limit: 1 Second      Memory Limit: 32768 KB ---- I guess...

30560
来自专栏数据结构与算法

BZOJ1053: [HAOI2007]反素数ant(爆搜)

  对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足:g(x)>g(i) 0<i<x

10020
来自专栏c#开发者

Processing Binary Documents Through BizTalk Via Web Services[转]

Published 21 July 06 08:24 AM | rseroter Just finishing up a two-week BizTalk P...

36140
来自专栏pangguoming

Node.js 开发模式(设计模式)

Asynchronous code & Synchronous code As we have seen in an earlier post (here), ...

32070

扫码关注云+社区

领取腾讯云代金券