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
",ans);
    }

    return 0;
}