杭电 2111 Saving HDU (贪心)
2024-09-30 05:05:02
Description
话说上回讲到海东集团面临内外交困,公司的元老也只剩下XHD夫妇二人了。显然,作为多年拼搏的商人,XHD不会坐以待毙的。
一天,当他正在苦思冥想解困良策的时候,突然想到了自己的传家宝,那是公司成立的时候,父亲作为贺礼送来的一个锦囊,徐父当时交代,不到万不得已的时候,不要打开它。“现在不正是最需要的时候吗?”,一边想,XHD一边找到了这个精心保管的锦囊,打开一看,里面只有一句话“杭城北麓千人洞有宝”。
二话不说,XHD拿起一个大口袋就出发了,这个千人洞他是知道的,小的时候,爸爸曾经带他来过这个隐蔽的路口,并告诉他,这是千人洞。他现在才明白爸爸当初这句话的含义。
尽管有点印象,XHD还是花了很大的精力才找到这个异常隐蔽的洞口,走进一看,几乎惊呆了,真的是眼花缭乱!不过尽管宝贝的种类不少,但是每种宝贝的量并不多,当然,每种宝贝单位体积的价格也不一样,为了挽救HDU,现在请你帮忙尽快计算出来XHD最多能带回多少价值的宝贝?(假设宝贝可以分割,分割后的价值和对应的体积成正比)
一天,当他正在苦思冥想解困良策的时候,突然想到了自己的传家宝,那是公司成立的时候,父亲作为贺礼送来的一个锦囊,徐父当时交代,不到万不得已的时候,不要打开它。“现在不正是最需要的时候吗?”,一边想,XHD一边找到了这个精心保管的锦囊,打开一看,里面只有一句话“杭城北麓千人洞有宝”。
二话不说,XHD拿起一个大口袋就出发了,这个千人洞他是知道的,小的时候,爸爸曾经带他来过这个隐蔽的路口,并告诉他,这是千人洞。他现在才明白爸爸当初这句话的含义。
尽管有点印象,XHD还是花了很大的精力才找到这个异常隐蔽的洞口,走进一看,几乎惊呆了,真的是眼花缭乱!不过尽管宝贝的种类不少,但是每种宝贝的量并不多,当然,每种宝贝单位体积的价格也不一样,为了挽救HDU,现在请你帮忙尽快计算出来XHD最多能带回多少价值的宝贝?(假设宝贝可以分割,分割后的价值和对应的体积成正比)
Input
输入包含多个测试实例,每个实例的第一行是两个整数v和n(v,n<100),分别表示口袋的容量和宝贝的种类,接着的n行每行包含2个整数pi和mi(0<pi,mi<10),分别表示某种宝贝的单价和对应的体积,v为0的时候结束输入。
Output
对于每个测试实例,请输出XHD最多能取回多少价值的宝贝,每个实例的输出占一行。
Sample Input
2 2
3 1
2 3
0
Sample Output
5
单价是每体积的单价
#include<cstdio>
#include<algorithm>
using namespace std;
struct stu
{
int a,b;
}a[];
bool cmp(stu a,stu b)
{
return a.a>b.a;
}
int main()
{
int m,n,i,j;
int sum;
while(scanf("%d %d",&m,&n) && m)
{
sum=;
for(i=; i < n; i++)
{
scanf("%d %d",&a[i].a,&a[i].b);
}
sort(a,a+n,cmp);
for(i=;i<n;i++)
{
if(m > a[i].b)
{
sum+=(a[i].a*a[i].b);
m-=a[i].b;
}
else
{
sum+=(a[i].a*m);
break;
}
}
printf("%d\n",sum);
}
}
最新文章
- 启动调试IIS时,vs无法在 Web 服务器上启动调试。Web 服务器未能找到请求的资源。 有关详细信息,请单击“帮助”。
- java 的 sqlHelper,改改之后也适用于不使用 EF 的 C# 项目,包含查询和建表。
- SQLServer idenity 字段跳值
- setsockopt 设置 SO_LINGER 选项
- visual.studio.15.preview5 编译器
- Nginx 工作原理和优化、漏洞
- java中 正则表达式的使用
- Android开发之Intent跳转到系统应用中的拨号界面、联系人界面、短信界面
- 开发错误日志之Unix/Linux命令未执行或无结果等且程序无错误
- C++中使用class和structkeyword的不同
- [C#、winform] FormDesigner.cs报错The variable &#39;xxxxxx&#39; is either undeclared or was never assigned
- iOS多线程的三种方法
- 团队作业2--需求分析&;原型设计
- ThinkPhp 添加模型类
- java获取ip的方式,注意多级代理的方式获取
- (五十五)iOS多线程之GCD
- 手把手使用Git?
- MOOC Linux内核之旅小结【转】
- 【Visual Studio 扩展工具】如何在ComponentOne的DataTree中实现RightToLeft布局
- IDEA的maven项目中 静态文件编译的问题
热门文章
- 理解C++中拷贝构造函数
- bzoj2333[SCOI2011]棘手的操作 洛谷P3273 [SCOI2011]棘手的操作
- AJPFX关于File类复习
- 微信小程序组件解读和分析:十二、picker滚动选择器
- iOS Programming UIWebView 2
- [Android]如何实现无限滚动的ListViw/GridView(翻译)
- SQL Server中行列转置方法
- android手机web网站拨打电话几种方式
- js 或jquery定义方法时,参数不固定是怎么实现的
- java线程池,信号量使用demo