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;
}