一道简单的贪心题,有个问题求大佬帮忙看一下
题目链接: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; }