题意:
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; }