poj1018解题报告

//我是莱鸟,多多交流

//380k

//94ms

题目的意思是:每种装备可由多个生产商提供,从每一种装备中选择一个厂家的设备,使得所选的总的各种装备中的最小带宽B与他们的价格之和P的比值B/P达到最大。

解题思路:

准备工作:在输入时,统计所有装备中的最小值min,和每种装备中的最大值max,然后从最大值中选出最小的一个Max。

然后:从最小值min到Max之间枚举所有的可能的结果,并输出最大的一个值

1、对每种装备进行按p的大小进行升序快排。以便之后的查找工作。

2、保存min到Max之间的所有的的B的节点及他们所在行列数,便于之后查询。

3、对min到Max之间的B[i]进行枚举,并进行更新。

4、输出最大的值。

#include <stdlib.h>
#include <stdio.h>
typedef struct Node
{
int bb;
int p;
}Node;
typedef struct BID
{
int bb;//带宽值
int row;//所在的行号
int col;
}BID;
Node node[101][101];//保存节点
BID B[10001];//保存需要枚举的带宽B值
int comp(const void *a,const void *b)
{
BID* x=(BID*)a;
BID* y=(BID*)b;
if(x->bb==y->bb)
{
if(x->row==y->row)
return x->col-y->col;
return x->row-y->row;
}
return x->bb-y->bb;
}
int cmp(const void *a,const void *b)
{
return ((Node*)a)->p-((Node*)b)->p;
}
int main()
{
void search(int num,int index[]);
int max[101];//保存每组的P最大值
int index[101];//保存每行厂家的个数
int n,num;
int i,j,k;
scanf("%d",&n);
while(n-->0)//
{
int min=65535;//保存最小的P值
int count=0;
for(i=0;i<10001;i++)
B[i].bb=0;
scanf("%d",&num);//设备种数
for(i=0;i<num;i++)//输入一组测试数据
{
scanf("%d",&index[i]);
for(j=0;j<index[i];j++)//输入一行数据
{
scanf("%d %d",&node[i][j].bb,&node[i][j].p);
if(node[i][j].bb>max[i])
max[i]=node[i][j].bb;
if(node[i][j].bb<min)
min=node[i][j].bb;
}
}
int Max=65535;//保存最大中的最小P值
for(k=0;k<num;k++)
if(max[k]<Max)
Max=max[k];
for(i=0;i<num;i++) //对各种厂家的设备按P从大到小的顺序升序排序
qsort(node[i],index[i],sizeof(Node),cmp);
for(i=0;i<num;i++)
for(j=0;j<index[i];j++)
if(node[i][j].bb>=min&&node[i][j].bb<=Max)
{
B[count].bb=node[i][j].bb;
B[count].row=i;
B[count++].col=j;
}
qsort(B,count,sizeof(BID),comp); //对B中的值按b为第一关键字,row为第二,cow为第三关键字升序排序
search(num,index);
}
return 1;
}
void search(int num,int index[101])//按B[]中的顺序进行枚举,并不断更新
{
int k=0;
int i,j;
double result=0;
while(B[k].bb)
{
double sum=0;
if(k&&B[k].bb==B[k-1].bb&&B[k].row==B[k-1].row)
{
k++;
continue;
}
int flag=0;
for(i=0;i<num;i++)
{
if(i!=B[k].row)
{
for(j=0;j<index[i];j++)
if(node[i][j].bb>=B[k].bb)//保证每种装备都有一件,否则不更新
{
sum=sum+node[i][j].p;
flag=1;
break;
}
if(flag)
flag=0;
else
break;
}
}
if(i==num)
{
double average;
average=B[k].bb/(sum+node[B[k].row][B[k].col].p);//
if(average>result)
result=average;
}
k++;
}
printf("%.3lf\n",result);
}

更多相关文章
  • 题意和解决回路匹配的思路如同hdu3488 (这里我第一次想到最短路,但是对于有回路这个不知道怎么处理,后来看了别人的解题报告才知道KM匹配,但是看到KM之后就自己想...想了很久....还是不知道回路这个地方怎么匹配......其实应该这样来想....总共有N个城市....如果是要形成回路..那么 ...
  • http://poj.org/problem?id=1173 发现此题资料甚少,斗胆第一次写一份解题报告[题意]     输入 n(代表二进制位数) k(代表黑条白条总共有几条,条形码是以黑条开始的,再白黑交替出现) m(代表每条最多占多少个二进制位)     输出这种模式的条形码的有多少个?    ...
  • 题目大意:使用两个哈希表来解决哈希冲突的问题.假如现在有两个哈希表分别为:H1,H2 ,大小分别为:n1,n2:现有一数据X需要插入,其插入方法为: 1.计算index1 = X MOD N1,  若哈希表H1的index1位置没有保存数据,则直接将X保存到H1得index1:否则,若哈希表H1的i ...
  • 题目大意:输入一个偶数(x<32),输出这个偶数是由哪两个素数相加所得. 比如:一个偶数26,它可以是3+23,7+19,13+13,这些素数相加所得. 输入输出样例: Sample Input 3 4 26 100 Sample Output 4 has 1 representation(s ...
  • 本题大意: 用天平对一物品进行称重,现有重量不同的砝码,砝码的重量分别为:1,3,9,27,..,3^n.(n<20) 天平的右侧放砝码,左侧放物品或物品和砝码,使得左右两边的重量相等. 现有一个物品,计算左右两边应当分别放多少个多大的砝码才能使得天平平衡. 例如:现在有一个重量为21的物品, ...
  • 好几年没有做ACM了,感觉忘得差不多了,这个做着做着就打瞌睡了!言归正传,下面是我的解题思路: 首先的话,我们可以画一个函数图,以输入数组的下标为X轴,以数组的和为Y轴,当数组和小于零时,我们使用备用的数组和sum2和备用的最小下标min2,并用flag进行标记.具体实现可以参考代码. 需要注意的地 ...
  • 一.原题中文大意. 1      2       3      4       5      6         7     8 9     10       11    12      13     14       15    16 17    18      19    20       21 ...
  • Spring1F Dice(HDU 5012)解题报告及测试数据
    Dice Time Limit:1MS     Memory Limit:65536KB Description There are 2 special dices on the table. On each face of the dice, a distinct number was writt ...
一周排行