HDU 1789 Doing Homework again(贪心)

时间:2022-11-13 00:33:24

Doing Homework again

这只是一道简单的贪心,但想不到的话,真的好难,我就想不到,最后还是看的题解

【题目链接】Doing Homework again

【题目类型】贪心

&题意:

Ignatius有N项作业要完成。每项作业都有限期,如果不在限期内完成作业,期末考就会被扣相应的分数。给出测试数据T表示测试数,每个测试以N开始(N为0时结束),接下来一行有N个数据,分别是作业的限期,再有一行也有N个数据,分别是若不完成次作业会在期末时被扣的分数。求出他最佳的作业顺序后被扣的最小的分数。(每个作业费时一天)。

&题解:

这题刚看感觉挺简单,但是要写出来确实还差点,自己的想法不是太麻烦就是有bug.
这题有些像dp,但有d不出来,又想贪心.可以拍2种序,一是用time排序,二是用score排序.
我用的是score排序: 先按照score从大到小排序,然后开始选择,让当前的课排在其time上面,如果这一天已经被占用了,那么就往前循环,有位置了就安排,没了就ans+=score。

按照score从大到小排序,如果score相同,也不用管time的排序了,因为不管这时你的time是升序还是降序,不能用的总是那几个,所以不用再排序time了.

【时间复杂度】\(O(n^2)\)

&代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i--)
#define PI(A) cout<<(A)<<endl;
const int maxn = (int)1e3 + 9;
int n;
bool v[maxn];
struct node {
    int time,score;
    bool operator <(const node& A)const {
        return score==A.score?time>A.time:score>A.score;
    }
} no[maxn];
int main() {
    int T; cin>>T; while(T--) {
        cin>>n;
        rep(i,1,n) cin>>no[i].time;
        rep(i,1,n) cin>>no[i].score;
        sort(no+1,no+1+n);
        memset(v,0,sizeof(v));
        ll ans=0;
        rep(i,1,n) {
            int j;
            for(j=no[i].time; j>0; j--)
                if (!v[j]) { v[j]=1; break; }
            if (j==0) ans+=no[i].score;
        }
        PI(ans)
    }
    return 0;
}