这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1789
思路:这题的出的很好,不是简单的贪心。
我先开始还是按照以前的思路来,把扣分越大,且截止时间越小的的排序,其实不能。
我们来分析下,这里的贪心,就是保证作业在最后一天做完。
并且,要保证扣分也最小。
所以,把扣分按从大到小排序,若扣分相同,则按截止日期从小到达拍。并把这个作业放在截止日期前一天,若前一天有任务了,则继续向前,直到前面没空的,这时就必须得扣分了。(理解)
代码:
// Author: Tanky Woo
// HDOJ 1789
#include
#include
#include
#include
using namespace std;
typedef struct homework
{
int deadlines;
int score;
double per;
}Homework;
Homework work[1001];
bool flag[1001];
bool cmp(Homework a, Homework b)
{
//return !(a.per>b.per);
if(a.score != b.score)
return a.score>b.score;
else
return a.deadlines=1; --j)
if(flag[j] == 0)
{
flag[j] = 1;
break;
}
if(j == 0)
reduce += work[i].score;
}
printf("%d\n", reduce);
}
return 0;
}