Doing Homework again

点我挑战题目

题意分析

给出n组数据，每组数据中有每份作业的deadline和score，如果不能按期完成，则要扣相应score，求每组数据最少扣除的score是多少。

典型的贪心策略。

既然是要求最少的扣分，那么肯定是要先完成分数最多的。所以可以推出按照分数排序。那么最佳策略应该是在deadline当天完成作业，如果那天已经占用，只能在deadline-1天完成，如果那天也被占用了，就只能在deadline-2天完成……直到推到第1天，如果还被占用的话，那么这个作业肯定是完不成了，扣除相应分数。遍历完数据，判断有哪些作业没有完成，输出其分数之和即可。

代码总览

/*

    Title: HDOJ.1789

    Author: pengwill

    Date：2016-11-22

*/

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <string.h>

using namespace std;

struct hw{

    int dline;

    int score;

    bool fish;

}item[1005];

bool judge[1005];

int cmp(hw a, hw b)

{

    return a.score > b.score;

}

int main()

{

    int n;

    scanf("%d",&n);

    while(n--){

        memset(judge,0,sizeof(judge));

        memset(item,0,sizeof(item));

        int i,t,j;

        scanf("%d",&t);

        for(i = 0;i<t;i++){

            scanf("%d",&item[i].dline);

        }

        for(i = 0;i<t;i++){

            scanf("%d",&item[i].score);

            item[i].fish = false;

        }

        sort(item,item+t,cmp);

        for(i = 0;i<t;i++){

            for(j = item[i].dline;j>=1;j--){

                if(!judge[j]){

                    judge[j] = true;

                    item[i].fish = true;

                    break;

                }

            }

        }

        int ret = 0;

        for(i = 0;i<t;i++){

            if(item[i].fish == false){

                ret += item[i].score;

            }

        }

        printf("%d\n",ret);

    }

    return 0;

}