hdu 2570(欲張り)
13791 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=2570
細かい問題ですよ.
View Code
View Code
細かい問題ですよ.
View Code
#include
"
iostream
"
#include
"
algorithm
"
using
namespace
std;
int
main()
{
int
i,t;
int
n,v,w;
double
a[
110
];
cin
>>
t;
while
(t
--
)
{
cin
>>
n
>>
v
>>
w;
for
(i
=
0
;i
<
n;i
++
) cin
>>
a[i];
sort(a,a
+
n);
double
p
=
0.0
;
int
k
=
0
;
for
(i
=
0
;i
<
n;i
++
)
{
if
((p
*
i
+
a[i])
/
(i
+
1
)
<=
w)
//
(sum*i*v+a[i]*v)/((i+1)*v)
{
p
=
(p
*
i
+
a[i])
/
((i
+
1
));
}
else
break
;
}
printf(
"
%d %.2lf
"
,i
*
v,p
/
100
);
}
return
0
;
}
次はこれが最初の方法です.vを少なく乗りましたので、wはn回、悲劇!View Code
#include
"
iostream
"
#include
"
algorithm
"
using
namespace
std;
int
main()
{
int
t,i,j;
int
n,v,w;
int
a[
110
];
cin
>>
t;
while
(t
--
)
{
cin
>>
n
>>
v
>>
w;
for
(i
=
0
;i
<
n;i
++
) cin
>>
a[i];
sort(a,a
+
n);
double
sum
=
0
,s
=
0
;
__int64 k
=
0
;
int
t
=
1
;
for
(i
=
0
;i
<
n;i
++
)
{
s
+=
a[i]
*
v;
//
V, n , , !
if
(s
/
(v
*
(i
+
1
))
<=
w)
{
sum
=
s
/
(v
*
(i
+
1
));
k
++
;
}
else
break
;
}
printf(
"
%I64d %.2lf
"
,k
*
v,sum
/
100
);
}
return
0
;
}