（C++)HDU-1789——作业（贪心算法）

秒速五厘米 2021-12-03 05:41 325阅读 0赞

### 题目描述 ###

交大校队刚从2018焦作站ACM/ICPC回来。现在他有很多作业要做。每个老师给他一个交作业的最后期限。  
如果他们在最后期限后交作业，老师就会降低他的期末成绩。  
现在我们假设每个人做作业都需要一天。  
所以他们想到了要安排做作业的顺序，把降低的分数降到最低。  
请帮助他们。

#### *input* ####

输入包含T个测试用例。输入的第一行是单个整数T，为测试用例的数量。  
每个测试用例以一个正整数N开头(1<=N<=1000)，表示作业的数量。  
然后两行。第一行包含N个整数，表示受试者的截止日期，下一行包含N个整数，表示降低的分数。

#### *output* ####

对于每个测试用例，您应该输出最小的总降低分数，每个测试用例一行。

### 题目解析 ###

很明显，这道题需要贪心的思想，那么该怎么贪心呢？

*  首先贪心的一点为既然要损失最少的分数，那我一定要做完分值最高的作业
 *  但是还要更贪心哦，我还要必须在最后一天去做那个分值最高的作业，来为我的其他作业留出时间

这样思考的话，就可以得到该题的解决思路：

*  首先根据分值从大到小对作业进行排序
 *  将分值最大的作业安排在它的截止日期当天，分值第二大的作业也安排在它自己的截止日期当天，如果正好那天已经安排了作业，则往前推一天做，以此类推，最后没有时间做的作业就加到损失分数上

### 源代码（可AC） ###

#include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    struct Work
    {
        
        int dl;
        int loss;
    }a[1010];
    bool cmp(Work& a,Work& b)
    {
        
        return a.loss>b.loss;
    }
    int day[1010];
    int main()
    {
        
        int t;
        cin>>t;
        while(t--)
        {
        
            memset(day,0,sizeof(day));
            int n,ans=0;
            cin>>n;
            for(int i=0;i<n;++i)
                cin>>a[i].dl;
            for(int i=0;i<n;++i)
                cin>>a[i].loss;
            sort(a,a+n,cmp);
            //cout<<a[0].dl<<' '<<a[0].loss<<endl;
            for(int i=0;i<n;++i)
            {
        
                int flag=0;
                for(int j=a[i].dl;j>=1;--j)
                {
        
                    if(day[j]==0)
                    {
        
                        day[j]=a[i].loss;
                        flag++;
                        break;
                    }
                }
                if(flag==0)
                    ans+=a[i].loss;
            }
            cout<<ans<<endl;
        }
    }