2109:每个房间有一只猫看守javabean。 每只猫需要的猫粮和守卫的javabean数目不等。现在有一定数量猫粮,求最多能换出多少javabean.
思路:贪心。总是选最少猫粮换最多javabean的房间,即效率最高的那个。
#include<iostream>
using namespace std;
#include<stdio.h>
#include<algorithm>
#include<vector>
struct Room
{
int javabean;
int food;
double weight;
};
bool compare(Room a,Room b)
{
return a.weight > b.weight;
}
int main ()
{
vector<Room> v;
int m;
int n;
double sum;
while(1)
{
cin>>m;
cin>>n;
sum=0;
v.clear();
if(m==-1&&n==-1)
break;
while(n--)
{
Room r;
cin>>r.javabean;
cin>>r.food;
r.weight=(double)r.javabean/r.food;
v.push_back(r);
}
sort(v.begin(),v.end(),compare);
for(int i=0;i<v.size();i++)
{
if(m>v[i].food)
{
sum += v[i].javabean;
m -= v[i].food;
}
else
{
sum += (double)m*v[i].javabean/v[i].food;
break;
}
}
printf("%.3f\n",sum);
}
}
分享到:
相关推荐
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
ZOJ完全解题报告,喜欢ACM的同学,欢迎下载
zoj 1140-zju 2433 简单题的部分答案 都是可以正确通过的,简洁易懂
zoj 3590 -3+1.md
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
zoj 3212 K-Nice.md
zoj 2561 Order-Preserving Codes.md
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
NULL 博文链接:https://weitch.iteye.com/blog/1006972
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
一个非常非常非常非常实用的zoj结题代码
zoj 2536 这个不是用贪心做的
最新版硬件信息查询工具EVEREST Ultimate Edition Code:HJ8ZOJ-H307UX-0AA9RF-XFTD007