哈哈哈HDU1009+HDU2037 简单贪心法清晰讲解
程序员文章站
2023-12-31 15:23:10
...
标题HDU 1009和HDU 2037
两道比较简单的贪心题;
先贴原题:!!
1009:
题目大意:铲屎官拿手里的猫食和猫的仓库里换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(节目安排)
原题:
题目大意:
你要在暑假看电视节目(废话),然后我给你很多节目单(无序的),求你能完整看完的节目的最大数,比如你看回家的诱惑的时候你就不能看别的节目,必须看完,才能看下一个节目。
贪心依据:把节目按结束时间排序,那么第一个节目肯定是你要看的,所有答案至少为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;
}
就要和大家说再见了
先说一下 我菜的真实,如果有哪里不对的地方,请大佬一定指出来,拜托!
一定要指出来!