#include
<
iostream
>
#include
<
set
>
#include
<
limits
>
using
namespace
std;
![](/Images/OutliningIndicators/None.gif)
struct
Node
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int
broad, price;
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
Node()
{}
Node(
int
&
a,
int
&
b)
:broad(a),price(b)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{}
}
;
![](/Images/OutliningIndicators/None.gif)
Node data[
100
][
100
];
int
length[
100
];
![](/Images/OutliningIndicators/None.gif)
![](/Images/OutliningIndicators/None.gif)
int
main()
![](/Images/OutliningIndicators/ExpandedBlockStart.gif)
{
int
test;
scanf(
"
%d
"
,
&
test);
![](/Images/OutliningIndicators/InBlock.gif)
while
( test
--
)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int
n;
set
<
int
>
br;
![](/Images/OutliningIndicators/InBlock.gif)
scanf(
"
%d
"
,
&
n);
![](/Images/OutliningIndicators/InBlock.gif)
for
(
int
i
=
0
; i
<
n;
++
i )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int
d,x,y;
scanf(
"
%d
"
,
&
d);
![](/Images/OutliningIndicators/InBlock.gif)
length[i]
=
d;
for
(
int
j
=
0
; j
<
d;
++
j )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf(
"
%d%d
"
,
&
x,
&
y);
data[i][j]
=
Node(x,y);
![](/Images/OutliningIndicators/InBlock.gif)
br.insert(x);
//
Save all broad , use set to avoid repeating
}
}
set
<
int
>
::iterator pos;
double
max
=
numeric_limits
<
double
>
::min();
for
( pos
=
br.begin (); pos
!=
br.end ();
++
pos )
//
for every broad
{
int
t
=
*
pos;
int
total
=
0
;
bool
isok
=
false
;
![](/Images/OutliningIndicators/InBlock.gif)
for
(
int
i
=
0
; i
<
n;
++
i )
//
n devices
{
int
M
=
INT_MAX;
![](/Images/OutliningIndicators/InBlock.gif)
for
(
int
j
=
0
; j
<
length[i];
++
j )
if
( data[i][j].broad
>=
t
&&
data[i][j].price
<
M )
M
=
data[i][j].price;
//
find the min price
if
( M
==
INT_MAX )
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
isok
=
true
;
break
;
}
total
+=
M;
}
if
( isok )
continue
;
![](/Images/OutliningIndicators/InBlock.gif)
if
( (
double
)t
/
(
double
)total
>
max ) max
=
(
double
)t
/
(
double
)total;
//
update
}
printf(
"
%.3lf\n
"
, max );
}
return
0
;
}
posted on 2008-10-01 22:06
Darren 阅读(506)
评论(2) 编辑 收藏 引用 所属分类:
图论 、
搜索