题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1789

题目描述

Ignatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline of handing in the homework. If Ignatius hands in the homework after the deadline, the teacher will reduce his score of the final test. And now we assume that doing everyone homework always takes one day. So Ignatius wants you to help him to arrange the order of doing homework to minimize the reduced score.

思路

贪心算法,先从按分数从大到小排序,分数一样截止日期从小到大排序。

然后用个数组记录每天是否做过作业。

AC代码

/*************************************************************************
    > File Name: 1789.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-06-08 Mon 23:03:07 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

struct hw {
    int dl, rs;
    friend bool operator<(const hw &a, const hw &b) {
        if(a.rs == b.rs)   // 按分数从大到小排序,分数一样截止日期从小到大排序。
            return a.dl <  b.dl;
        return a.rs > b.rs;
    }
}hw[1001];

int main()
{
#ifdef Oj
    freopen("1789.in", "r", stdin);
#endif
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> hw[i].dl;
        for (int i = 0; i < n; ++i)
            cin >> hw[i].rs;
        sort(hw, hw+n); // 按分数从大到小排序,分数一样截止日期从小到大排序。
        static bool tday[1000]; // 记录每天是否使用过
        int ans = 0;
        memset(tday, 0, sizeof(tday));
        for (int i = 0; i < n; ++i) {
            int day;
            for (day=hw[i].dl; day>0; --day)
                if(!tday[day])  { // 在截止日期内有一天未做作业,则使用
                    tday[day]= true;
                    break;
                }
                if(day == 0) // 都用过了,则无法完成
                    ans+=hw[i].rs;
        }
        cout << ans << endl;
    }
    return 0;
}