zoj 2109 简单贪心背包

最新推荐文章于 2019-08-08 14:07:46 发布

原创最新推荐文章于 2019-08-08 14:07:46 发布 · 399 阅读

0 ·

CC 4.0 BY-SA版权

ZOJ 专栏收录该内容

37 篇文章

订阅专栏

本文介绍了一个使用C++实现的程序，在该程序中探讨了通过sort替代qsort所带来的性能改进。文章详细解释了如何定义一个结构体来保存必要的数据，并且提供了一个比较函数用于排序这些结构体元素。通过对特定条件的迭代，程序最终计算并输出了一个累积值。

用qsort过不了，sort就过了不知道为什么

#include<stdio.h>
#include<stdlib.h> 
#include<string.h>
#include <algorithm> 
using namespace std;
struct fm{
	int j,f;
	double jperf;
} cat[1010];
bool cmp( struct fm a,struct fm b )  
{  
    return a.jperf>b.jperf;  
}  
  
int main(){
	int m,n;
	while(scanf("%d%d",&m,&n)&&m>=0&&n>=0){
		int i;
		for(i = 0;i<n;i++){
			scanf("%d%d",&cat[i].j,&cat[i].f);
			cat[i].jperf = cat[i].j *1.0 / cat[i].f;
		}
		sort(cat,cat + n,cmp);
		i = 0;
		double jb = 0;
		while(m>0&&i<n){
			if(cat[i].f<m){
				m -= cat[i].f;
				jb += cat[i].j;
			}
			else {
				jb += cat[i].jperf*m;
				m = 0;
			}
			i++;
		}
		printf("%.3lf\n",jb);
	}
	return 0;
}