首页 > 代码库 > hdu 1789 Doing Homework again（贪心）
hdu 1789 Doing Homework again（贪心）
题意：
N个作业，每个作业有个deadline。每个作业完成耗时一天。
如果某个作业没在deadline前完成，则要扣去一定的分数。
给出N个要扣除的分数score[1]....score[N]。
如何安排使得扣分最少？求最少扣分。
思路：
按扣分多少从大到小排序，然后一个一个放到各自的deadline前的某个位置，哪个位置？
哪个位置有空就放那儿，且必须要都靠后！也就是从后往前放。这样可以保证最优地不占用更靠前的别人的deadline前的空间。
具体看代码，，，，
代码：
struct node{ int deadtime, score;}a[1005];int b[100005];bool cmp(node a,node b){ if(a.score==b.score) return a.deadtime<b.deadtime; return a.score>b.score;}int Insert(int deadtime){ rep2(i,deadtime,1){ if(b[i]==-1) return i; } return -1;}int T,n;int main(){ int T; cin>>T; while(T--){ scanf("%d",&n); rep(i,1,n) scanf("%d",&a[i].deadtime); rep(i,1,n) scanf("%d",&a[i].score); sort(a+1,a+1+n,cmp); int ans=0; mem(b,-1); rep(i,1,n){ int pos=Insert(a[i].deadtime); if(pos!=-1){ b[pos]=i; }else{ ans+=a[i].score; } } printf("%d\n",ans); } return 0;}
hdu 1789 Doing Homework again（贪心）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。