贪心算法.我就不贴题了//no.1009
但是我的代码运行超时了…改了好久都不对…
看别人代码,顺便学习c++控制保留小数怎么操作;
我的错误代码:(时间占用可能是多次调用findmax造成的)
#include <iostream>
using namespace std;
int findmax(double [],int n);
int main()
{
int asset,nshop;
while(~scanf("%d%d",&asset,&nshop),asset,nshop)
{
int s[nshop-1][2],i;
double rate[nshop-1];
while (nshop--)
{
for (i = 0;i<nshop;i++)
{
scanf("%d%d",&s[nshop-1][0],&s[nshop-1][1]);
rate[i] = (double)s[nshop-1][0]/s[nshop-1][1];
}
}
int maxnum;
double ans = 0.0;
maxnum = findmax(rate,nshop-1);
while (s[maxnum][1]<=asset)
{
ans = ans+s[maxnum][0];
asset = asset-s[maxnum][1];
rate[maxnum] = 0.0;
maxnum = findmax(rate,nshop-1);
}
double r = s[maxnum][0]/(double)s[maxnum][1];
ans+=r*asset;
printf("%.3lf\n",ans);
}
return 0;
}
int findmax(double a[],int n)
{
int i,index = 0;
double max = a[0];
for (i = 0;i<n;i++)
if (a[i]>max)
{
index = i;
max = a[i];
}
return index;
}
ac代码:
#include <cstdio> //贪心
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M;
struct node{
int x,y;
double s;
}a[1000];
double cmp(node aa,node bb){
return aa.s>bb.s;
}
int main(){
double sum,ans,w;
int l,k;
while(~scanf("%d %d",&M,&N)){
if(M==-1&&N==-1) break;
for(int i=0;i<N;i++){
scanf("%d %d",&a[i].x,&a[i].y);
a[i].s=(1.0*a[i].x/a[i].y);
}
sort(a,a+N,cmp);//c++内置的sort算法
sum=0.0,ans=0.0;
for(int i=0;i<N;i++){
if(sum<=M){
if(sum+a[i].y<=M){
ans+=a[i].x;
sum+=a[i].y;
}
else{
ans+=a[i].s*(M-sum);
sum=M;
}
}
else {
break;
}
}
printf("%.3lf\n",ans);
}
return 0;
}
最好找时间再做一遍,看看掌握否
下面是c++控制输出:
#include <iomanip> //这是一定要有的头文件
//setprecision括号里的就是保留几位小数
cout<<fixed<<setprecision(2);//最简写法
//还有更复杂一些的写法,我不理解其意义
cout<<setiosflags(ios::fixed)<<setprecision(2);
//或者:
cout.setf(ios::fixed);
cout<<setprecision(2);
