Question

2570 大牛们请教，总是WA，思路跟HDU论坛上一样啊

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2570
#include <stdio.h>
int main()
{
int t,n;
double v,w,s,k,a;
double p[110],max,temp;
int i,j;
int local;
while(scanf("%d",&t)!=EOF)
{
while(t--)
{
scanf("%d%lf%lf",&n,&v,&w);
for(i=0;i<n;i++)
{
scanf("%lf",&p[i]);
}
for(i=n;i>0;i--)
{
max=p[0];
local=0;
for(j=0;j<i;j++)
if(max<p[j])
{
max=p[j];
local=j;
}
temp=p[i-1];
p[i-1]=p[local];
p[local]=p[i-1];
}
s=0;
k=0;
a=0;
for(i=0;i<n;i++)
{
a=a+p[i]/100*v; //a为溶质
s=a/(v*(k+1));
if(s<=w/100)
k++;
else
{
a=a-p[i]/100*v;
s=a/(v*(k));
}
}
printf("%.0lf %.2lf\n",k*v,k==0?0:s);
}
}
return 0;
}
请大家帮我看下哪里错，我郁闷一上午了

Answer 1

你代码的主要问题是实数的处理不到位，给你一组错误的数据，题目能用整数做就不要用实数做，实数在计算机当中的表示是近似值而不是准确值
1
2 1 6
5 7
（0.05+0.07不一定等于0.06+0.06哦）
对于实数的处理，一般给出一个误差eps，认为两个数只要在这个误差内，就算两个数相等

下面给出我的代码。
//Code by SCROOKE 2010-1-28 11:21:07
//Code for 紫英落 (baidu)
//HDU 2570

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
int n,p,q,r,s,t;
int a[100];
scanf("%d",&n);
while (n--)
{
scanf("%d%d%d",&p,&q,&t);
for (s=0;s<p;s++)
{
scanf("%d",&a[s]);
a[s]-=t;
}
sort(a,a+p);
r=0;
for (s=0;s<p;s++)
if (r+a[s]<=0)
r+=a[s];
else break;
if (s)
printf("%d %.2f\n",s*q,0.01*t+r*0.01/s);
else printf("%d %.2f\n",0,0);
}
return 0;
}

Answer 2

看了下自己的提交。没做过。
但是感觉可以用贪心算法解。

等我解解看

已解。AC代码如下，纯粹的贪心算法，重点在排序和溶质的计算
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
int n, v, w, a[101], i, vol, c;
double p;
cin >> c;
while (c--){
cin >> n >> v >> w;
vol = 0;
p = 0;
for (i = 1; i <= n; i++){
cin >> a[i];
}
sort(&a[1], &a[n] + 1);
for (i = 1; i <= n; i++){
if ((vol * p + v * a[i]) / (vol + v) > w)
break;
else{
p = (vol * p + v * a[i]) / (vol + v);
vol += v;
}
}
printf("%d %.2lf\n", vol, p / 100);

}
}