HDU1789 Doing Homework again 做作业【贪心】

题目链接：https://vjudge.net/problem/HDU-1789

 

题目大意：

给出N个作业的截至日期，和N个作业不交所扣掉的分数，要求输出扣除分数做少的方案。

 

解析：

与上一道销售商品类似，将分数从大到小排序，找到deadline，如果它的期限没有被占用，就在该天写完，然后vis置1，如果占用，则从它的前一天开始向前查找有没有空闲的日期，如果有则占用,vis置1。这样就可以得到最大分数。然后用总分数减去得到最大分数即为扣除的最小分数。

#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 1000+10
int vis[MAXN];

struct node
{
    int day, sco;
};

bool mycmp(node a, node b)
{
    return a.sco > b.sco;
}

int main()
{
    int t, n;
    while (scanf("%d", &t) != EOF)
    {
        int i, j;
        while (t--)
        {
            
            memset(vis, 0, sizeof(vis));
            node a[MAXN];
            scanf("%d", &n);
            int maxday = 0; int sum = 0;
            for (i = 0; i < n; i++)scanf("%d", &a[i].day);
            for (i = 0; i < n; i++)
            {
                scanf("%d", &a[i].sco);
                sum += a[i].sco;
            }
            int sumscore = 0;
            sort(a, a + n,mycmp);
            for (i = 0; i < n; i++)
            {
                if (!vis[a[i].day])
                {
                    vis[a[i].day] = 1;
                    sumscore += a[i].sco;
                }
                else
                {
                    for (j = a[i].day-1; j >= 1; j--)         //若该天已被占据，则向之前寻找没有占据的日期
                    {
                        if (!vis[j])
                        {
                            vis[j] = 1;
                            sumscore += a[i].sco;
                            break;
                        }
                    }
                }
            }
            printf("%d\n", sum - sumscore);
        }
    }
    return 0;
}

 

 

2018-04-21