首页 > 代码库 > HDU1789Doing Homework again(贪心)
HDU1789Doing Homework again(贪心)
HDU1789Doing Homework again(贪心)
题目链接
题目大意:给你n们作业的最后期限和过了这个期限没做需要扣的分数,问怎样安排可以使得扣分最少。
解题思路:贪心,将扣分多的作业排在前面,扣分相同的按照最后期限前的排前面,然后用一个数组来表示第i天是否有安排。每次都将第i个作业放到它的最后期限的那天完成,但如果这一天被占了,那么就只能往前移动,找空闲的天。如果一直找到了0,那么说明这个作业是无法按时完成了,就加上分数。如果某项作业完成的最后期限比n还大,那么这个作业一定是可以及时完成的,那么就可以不管它了。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 5;
int vis[maxn];
int n;
struct homework {
int deadt, score;
}h[maxn];
int cmp (const homework &a, const homework &b) {
if (a.score != b.score)
return a.score > b.score;
return a.deadt < b.deadt;
}
int solve () {
sort(h, h + n, cmp);
memset (vis, -1, sizeof (vis));
int ans = 0, time;
for (int i = 0; i < n; i++) {
time = h[i].deadt - 1;
if (time >= n)
continue;
while (time >= 0 && vis[time] != -1) {
time--;
}
if (time >= 0)
vis[time] = 1;
else
ans += h[i].score;
}
return ans;
}
int main () {
int T;
scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
for (int i = 0; i < n; i++)
scanf ("%d", &h[i].deadt);
for (int i = 0; i < n; i++)
scanf ("%d", &h[i].score);
printf ("%d\n", solve());
}
return 0;
}
HDU1789Doing Homework again(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。