zoj_2511 Design T-Shirt 贪心
Design T-Shirt
Time Limit: 2 Seconds Memory Limit: 32768 KB
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
思路: 把每一个元素的评分加总, 按评分降序排一下,相同评分内部再按照序号升序排一下。
#include <iostream>
#include <stdio.h>
#include <algorithm> using namespace std; struct dat
{
float num;
int index;
}data[]; bool cmp(dat a, dat b)
{
if(a.num != b.num)
return a.num > b.num;
else
return a.index < b.index;
} int main()
{
int n,m,k;
while(scanf("%d%d%d",&n,&m,&k)!=-)
{ float temp=;
for(int i=;i<m;i++)
{
data[i].num = ;
data[i].index = i;
}
for(int i=; i<=n; i++)
{
for(int j=; j<m; j++)
{
scanf("%f", &temp);
data[j].num += temp;
}
} sort(data, data+m, cmp); // for(int i=0; i<m; i++)
// {
// printf("%f---%d\n", data[i].num, data[i].index);
// } int ans[k+]; for(int i=; i<k; i++)
{
ans[i]=data[i].index+;
}
sort(ans, ans+k, greater<int>()); for(int i=; i<k; i++)
{
if(i!=k-)
printf("%d ",ans[i]);
else
printf("%d\n", ans[i]);
}
}
return ;
}
最新文章
- C#窗体程序【用户控件-窗体】委托事件
- 为什么xcode7请求不成功
- Repeater展示表格
- Connect to a Windows PC from Ubuntu via Remote Desktop Connection
- Test,Nginx Hello World Module
- 【Binary Tree Inorder Traversal】cpp
- ADO.NET基础02(语句参数化,配置文件,DataSet与DataTable)
- jquery easyui的方法参数
- GridView 中Item项居中显示
- (中等) HDU 5046 Airport ,DLX+可重复覆盖+二分。
- moment倒计时插件
- spoj1026Favorite Dice
- django登录逻辑
- P3258 [JLOI2014]松鼠的新家
- Java 中断异常的正确处理方式
- Python之路,第九篇:Python入门与基础9
- 搜集的一些酷炫的金属色 ,RGB值 和大家分享一下
- Unity3D自己常用代码
- 2018-2019 ACM-ICPC, Asia Seoul Regional Contest
- CSS实现子级窗口高度随低级窗口高度变化及js控制左右容器高度一致
热门文章
- Vertica的这些事(六)——-vertica中group-by-和join-语句的优化
- yii2框架学习笔记
- 好玩Python——PIL项目实训
- docker-compose中加入nginx 日志和部署下载
- Java第三十二天,IO操作(续集),读写缓冲区的使用
- 推荐一款超实用的GitHub可视化代码树插件:Octotree
- 29.3 ArrayList、List、LinkedList(链表)优缺点
- 29.1 collection层次结构 中的根接口
- Array(数组)对象-->;splice() 方法
- 怎么把jmeter汉化?