POJ1018贪心(多路归并的想法)
题意:
有n个服务器,每个服务器都要安装网线(必须也只能安装一个),然后每个服务器都有mi种选择网线的方式,每种方式两个参数,一个是速度b,另一个是价钱p,然后让你找到一个最大的比值 minb/sump,就是所有的选择中最小的那个速度,必上话的钱的总和。
思路:
这个题目按照讨论组里面的说法估计做法很多,不管了,说下我自己的做法吧,我的做法有点像操作系统里面那个多路归并(如果没记错是叫这个,做题的时候突然想到这个方式,试了下,还真行),具体是这样,枚举最小的b,也就是最小的那个带宽,对于每个服务器,我们可以先把他所有的可选择项都按照带宽从小到大排序,排序后再倒着预处理得到每个选项后面中最小的那个花费,全部这样处理完之后就得到了一个二维的表,然后我们开始枚举,每个表都是根据带宽从小到大排序的,这样所有中最小的那个肯定就是某一个的第一项,我们O(n)的时间找到第一项,以这一项的带宽为最小带宽,花费是当前这个选项的花费,其他的就选最小的花费,然后删除找到的这一项,就这样一直找到头一个服务器的选项全都用完了位置,还有就是删除项的时候可以开一个一维数组,记录当前这个服务器已经用到第几项了,删除第i个服务器的当前项,直接mk[i]++就行了,16msAC,总的时间复杂度最坏应该是
O(n*n*n) 1000000吧。感觉思路有点瞎扯了,呵呵,题目不难,瞎扯就瞎扯吧,好就说这些。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 100 + 10
#define INF 1000000000
using namespace std;
typedef struct
{
int b ,p ,minp;
}NODE;
NODE node[N][N];
int now[N] ,num[N];
bool camp(NODE a ,NODE b)
{
return a.b < b.b;
}
int main ()
{
int t ,i ,j ,n ,tmp ,sn;
scanf("%d" ,&t);
while(t--)
{
scanf("%d" ,&n);
for(i = 1 ,sn = 0 ;i <= n ;i ++)
{
scanf("%d" ,&num[i]);
sn += num[i];
for(j = 1 ;j <= num[i] ;j ++)
scanf("%d %d" ,&node[i][j].b ,&node[i][j].p);
sort(node[i] + 1 ,node[i] + num[i] + 1 ,camp);
for(j = num[i] ;j >= 1 ;j --)
{
if(j == num[i] || tmp > node[i][j].p)
tmp = node[i][j].p;
node[i][j].minp = tmp;
}
now[i] = 1;
}
double Ans = 0;
int nowb ,nowp;
while(sn--)
{
nowb = INF;
nowp = 0;
int mkbreak = 0;
for(i = 1 ;i <= n ;i ++)
{
if(now[i] > num[i]) mkbreak = 1;
if(nowb > node[i][now[i]].b)
nowb = node[i][now[i]].b;
}
if(mkbreak) break;
int mk = 0;
for(i = 1 ;i <= n ;i ++)
{
//if(now[i] > num[i]) continue;
if(!mk && nowb == node[i][now[i]].b)
{
mk = 1;
nowp += node[i][now[i]].p;
now[i] ++;
}
else nowp += node[i][now[i]].minp;
}
if(Ans < nowb * 1.0 / nowp)
Ans = nowb * 1.0 / nowp;
}
printf("%.3lf\n" ,Ans);
}
return 0;
}
最新文章
- ascii、unicode、utf、gb等编码详解
- python之初级学习
- php : 收集整理的非常有用的函数
- 回文字算法(java版本)
- CentOS下crond定时任务详细介绍
- 关于C# winform中使用pictureBox显示大红叉的原因
- EBS 用户及其联系人的失效时间
- Export-XLSX PowerShell generate real Excel XLSX files without Excel and COM
- 每日一“酷”之textwrap
- 动态Linq(结合反射)
- JS年月日三级联动下拉框日期选择代码
- 一张地图,告诉你NodeJS命令行调试器语句
- 百行go代码构建p2p聊天室
- 为什么String类是不可变的?
- python——jieba分词过程
- sql 存储过程参数为空则不作为条件
- Ubuntu 安装 H3C iNode 客户端
- 洛谷.3224.[HNOI2012]永无乡(Splay启发式合并)
- [ASP.NET MVC]视图是如何呈现的
- UESTC - 1057 秋实大哥与花 线段树模板题
热门文章
- 普通的一天,说一个普通的XML
- FreeBSD安装xorg + xfce 4
- XUPT-D
- python数据分析三剑客基础之matpoltlib初解
- 【Azure 服务总线】详解Azure Service Bus SDK中接收消息时设置的maxConcurrentCalls,prefetchCount参数
- 后台开发-核心技术与应用实践--TCP协议
- Centos7安装maven详情以及配置
- 第14 章 : Kubernetes Service讲解
- redis的主从复制(哨兵模式)
- 【spring cloud hoxton】Ribbon 真的能被 spring-cloud-loadbalancer 替代吗