杭电1009哪位大侠帮忙看看

发布网友发布时间：2024-01-20 04:24

共1个回答

热心网友时间：2024-01-22 09:24

// 帮你改完了，AC代码如下
// ans+=(double)M*T[i].J/T[i].F;这一句是很重要否则，精度会下降，我也曾经因为这样浪费了一个多小时......
// 除此之外，你的排序写的不对，最后贪心的过程也有错误......
#include<iostream>
using namespace std;

typedef struct Room{
int F;//pay
int J;//get
double ConRate;//conversionrate
}Room;
Room T[1000];

int main()
{
//freopen("1.txt","r",stdin);
int M,N;//M是老鼠有的数 N是有几个房间
int i,j,Sum;
Room temp;
while(cin>>M>>N&&M!=-1&&N!=-1)
{
Sum=M;
for(i=0;i<N;i++)
{
cin>>T[i].J>>T[i].F;
T[i].ConRate=(double)T[i].J/T[i].F;
}
/*********** sort ***************/
for(i=0;i<N-1;i++)
{
for(j=0;j<N-1-i;j++)
{
if(T[j].ConRate<T[j+1].ConRate)
{
temp=T[j]; T[j]=T[j+1]; T[j+1]=temp;
}
}
}
/*********** cal **************/
//for(i=0;i<N;i++) cout<<T[i].ConRate<<" ";
double ans=0.0;
for (i = 0; i < N; i++)
{
if(M>=T[i].F)
{
ans+=T[i].J;
M-=T[i].F;
// m++;
}
else
{
ans+=(double)M*T[i].J/T[i].F;
break;
//Sum-=Sum;
}
}
printf("%.3lf\n",ans);
//cout<<ans<<endl;
}
return 0;
}