hdu1789-经典贪心

发布于 2019-07-19  1.2k 次阅读


问题传送

题意:

有t组测试数据,每组测试数据中有n门功课,
第一行是完成它们的最晚时间限制,第二行是未在限制的时间内完成对应的任务要扣除的分数
需要设计一个完成任务的次序,使得扣的分数最少。输出最少扣的分数。
每天只能完成一个任务。

分析:

需要设计一个贪心策略。

一开始我想的是按照时间限制,从小到大排序,如果有时间相同时间的话,和前面最小的分数换位置。

这样想法是错误的! 

目的是让扣除的分数最小,那么必然,分数大的任务一定要完成。

所以应该按照分数 降序 排列。 

然后遍历一遍。

对于排过序后的每个任务,尽量晚完成。所以要从它的限定时间开始往前枚举,

如果某天没有被标记,就用这一天来完成这个任务。

如果某天被标记,说明这一天已经完成了别的任务,继续向前枚举。

当枚举到 0 时,说明这个任务无法完成,需要扣分。

代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long LL;

const int MAXN = 1005;

struct Node
{
    int Ti_e;
    int v;
}a[MAXN];

bool cmp(Node a, Node b)
{
    return a.v > b.v;
}

int vis[MAXN];

int main()
{
    int T, n;
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> a[i].Ti_e;
        for (int i = 0; i < n; i++)
            cin >> a[i].v;
        for (int i = 0; i < 1001; i++)
            vis[i] = 1;

        sort(a, a+n, cmp);
        int ans = 0,f;
        for (int i = 0; i < n; i++)
        {
            f = 1;
            for (int j = a[i].Ti_e; j >= 1; j--)
            {
                if (vis[j]) {
                    vis[j] = 0;
                    f = 0;     
                    break;
                }
            }
            if (f) 
                ans += a[i].v;
        }
        cout << ans << endl;
    }
    return 0;
}

Simple And Clear