一道简单的贪心题,有个问题求大佬帮忙看一下
题目链接:https://问题:题目里说每种月饼数量和总价格都是整数,但是这道题定义成int有一个测试点过不去,定义成double就过了,求大佬帮忙看一看怎么回事?
有一个点过不去的代码:
程序代码:#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<functional>
#include<iomanip>
#define LL long long
using namespace std;
int N,D;
struct node{
int sum;//两个变量定义成int
int price;
double a;
}cake[1010];
bool cmp(node s1,node s2){
return s1.a>s2.a;
}
int main(void){
cin>>N>>D;
int i;
for(i=1;i<=N;i++) cin>>cake[i].sum;
for(i=1;i<=N;i++) cin>>cake[i].price;
for(i=1;i<=N;i++) cake[i].a=(double)cake[i].price/(double)cake[i].sum;//强制类型转换也加了
sort(cake+1,cake+1+N,cmp);
i=1;
double money=0.0;
while(D && i<=N){
if(D>=cake[i].sum){
D-=cake[i].sum;
money+=cake[i].price;
}
else{
money+=(double)D*cake[i].price/(double)cake[i].sum;
D=0;
}
i++;
}
cout<<fixed<<setprecision(2)<<money<<endl;
return 0;
}
能AC的代码:
程序代码:#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<functional>
#include<iomanip>
#define LL long long
using namespace std;
int N,D;
struct node{
double sum; //两个变量改成double
double price;
double a;
}cake[1010];
bool cmp(node s1,node s2){
return s1.a>s2.a;
}
int main(void){
cin>>N>>D;
int i;
for(i=1;i<=N;i++) cin>>cake[i].sum;
for(i=1;i<=N;i++) cin>>cake[i].price;
for(i=1;i<=N;i++) cake[i].a=cake[i].price/cake[i].sum;
sort(cake+1,cake+1+N,cmp);
i=1;
double money=0.0;
while(D && i<=N){
if(D>=cake[i].sum){
D-=cake[i].sum;
money+=cake[i].price;
}
else{
money+=(double)D*cake[i].price/cake[i].sum;
D=0;
}
i++;
}
cout<<fixed<<setprecision(2)<<money<<endl;
return 0;
}




