欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

哈哈哈HDU1009+HDU2037 简单贪心法清晰讲解

程序员文章站 2023-12-31 15:23:10
...

标题HDU 1009和HDU 2037

哈哈哈HDU1009+HDU2037 简单贪心法清晰讲解
两道比较简单的贪心题;
先贴原题:!!
1009:
哈哈哈HDU1009+HDU2037 简单贪心法清晰讲解
题目大意:铲屎官拿手里的猫食和猫的仓库里换javabeans吃(因为铲屎官喜欢这种豆子,所以就要换到尽可能多的豆子),但是猫咪不会白给他,要拿猫食来换,如何给的猫食不够,精明的猫咪就会按比例给铲屎官豆子;
贪心的依据:先换拿豆子比例高的那组数据(也就是性价比啦!)
废话不多说:
AC代码:

#include<stdio.h>
#include<algorithm>
using namespace std;
struct trade
{
	int beans, catfood;
	double rate;
}f[3003];
bool cmp(trade a, trade b)
{
	return a.rate > b.rate;
}
int main()
{
	int n, m;
	while (scanf_s("%d%d", &m, &n))
	{
		if (n == -1 || m == -1)
			break;
		for (int i = 0; i < n; i++)
		{
			scanf_s("%d%d", &f[i].beans, &f[i].catfood);
			f[i].rate = (double)f[i].beans / f[i].catfood;//注意数据类型转换!
		}
		sort(f, f + n, cmp);//按贪心依据排序
		double sum = 0;
		for (int i = 0; i < n; i++)
		{
			if (m > f[i].catfood)
			{
				sum += f[i].beans;
				m -= f[i].catfood;
			}
			else
			{
				sum += f[i].rate * m;
				m = 0;
				break;
			}
		}
		printf("%.3lf\n", sum);
	}
	return 0;
}

对吧还挺清楚的代码吧
嘤嘤嘤?

HUD2037(节目安排)
原题:
哈哈哈HDU1009+HDU2037 简单贪心法清晰讲解
题目大意:
你要在暑假看电视节目(废话),然后我给你很多节目单(无序的),求你能完整看完的节目的最大数,比如你看回家的诱惑的时候你就不能看别的节目,必须看完,才能看下一个节目。
贪心依据:把节目按结束时间排序,那么第一个节目肯定是你要看的,所有答案至少为1;只要后一个节目的开始时间晚于你在看的这个节目的结束时间,那么就是局部最优哟。

AC代码:

#include<stdio.h>
#include<algorithm>
using namespace std;
struct listed
{
	int begin, end;
}f[120];
bool cmp(listed a, listed b)
{
	return a.end < b.end;//按结束时间排序
}
int main()
{
	int n;
	while (scanf_s("%d", &n), n)
	{
		for (int i = 0; i < n; i++)
			scanf_s("%d%d", &f[i].begin, &f[i].end);
		sort(f, f + n, cmp);
		int ans = 1, temp = f[0].end;
		for (int i = 1; i < n; i++)
		{
			if (f[i].begin >= temp)
			{
				ans++;
				temp = f[i].end;//如果这个节目是我要看的,那么把temp更新成这个节目的结束时间,嘻嘻;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

哈哈哈HDU1009+HDU2037 简单贪心法清晰讲解

就要和大家说再见了
先说一下 我菜的真实,如果有哪里不对的地方,请大佬一定指出来,拜托!
一定要指出来!

相关标签: ACM 贪心 杭电

上一篇:

下一篇: