本文主要是介绍hdoj 1789 Doing Homework again 【贪心】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
贪心策略：先按分数从大到小排序，分数一样，再按时间从小到大排序 分最高的越靠近期限完成，越好 话不多说直接看代码
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1789
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::sort;
typedef struct{
int sco, time;
}str;
str s[1005];
bool vis[1005]; //标记第n天有没有被用
int cmp(str a, str b) //排序
{
if(a.sco == b.sco) return a.time < b.time;
return a.sco > b.sco;
}
int main()
{
int t, n, i, j;
scanf("%d", &t);
while(t --){
scanf("%d", &n);
for(i = 0; i < n; i ++)
scanf("%d", &s[i].time);
for(i = 0; i < n; i ++)
scanf("%d", &s[i].sco);
memset(vis, 0, sizeof(vis));
int sum = 0;
sort(s, s+n, cmp);
for(i = 0; i < n; i ++){
for(j = s[i].time; j >= 1; j --){ //按照时间从后往前查找没有被用过的天数
if(!vis[j]){
vis[j] = 1;
break;
}
}
if(j == 0) //如果找到最后都被用了 就算是该分数拿不到了
sum +=s[i].sco;
}
printf("%d\n", sum);
}
return 0;
}
这篇关于hdoj 1789 Doing Homework again 【贪心】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
