HDU1789Doing Homework again（貪心）

HDU1789Doing Homework again（貪心）

HDU1789Doing Homework again（貪心）

題目鏈接

題目大意:給你n們作業的最後期限和過了這個期限沒做需要扣的分數，問怎樣安排可以使得扣分最少。

解題思路：貪心，將扣分多的作業排在前面，扣分相同的按照最後期限前的排前面，然後用一個數組來表示第i天是否有安排。每次都將第i個作業放到它的最後期限的那天完成，但如果這一天被占了，那麼就只能往前移動，找空閒的天。如果一直找到了0，那麼說明這個作業是無法按時完成了，就加上分數。如果某項作業完成的最後期限比n還大，那麼這個作業一定是可以及時完成的，那麼就可以不管它了。

代碼：

#include 
#include 
#include 

using namespace std;

const int maxn = 1e3 + 5;
int vis[maxn];

int n;
struct homework {

    int deadt, score;
}h[maxn];

int cmp (const homework &a, const homework &b) {

    if (a.score != b.score)
        return a.score > b.score;
    return a.deadt < b.deadt;
}

int solve () {

    sort(h, h + n, cmp);
    memset (vis, -1, sizeof (vis));

    int ans = 0, time;
    for (int i = 0; i < n; i++) {

        time = h[i].deadt - 1;
        if (time >= n)
            continue;
        while (time >= 0 && vis[time] != -1) {
            time--;
        }

        if (time >= 0)
            vis[time] = 1;
        else
            ans += h[i].score;
    }
    return ans;
}

int main () {

    int T;
    scanf ("%d", &T);
    while (T--) {

        scanf ("%d", &n);
        for (int i = 0; i < n; i++)
            scanf ("%d", &h[i].deadt);
        for (int i = 0; i < n; i++)
            scanf ("%d", &h[i].score);

        printf ("%d\n", solve());    
    }
    return 0;
}