贪心策略:按照分数降序排列,如果分数相同将截止时间早的排在前面。每次让作业尽量晚完成,因此需要逆序枚举判断这一天是否已经做了其他作业,如果没时间做这个作业说明不能完成,否则将这一天标记。
AC代码
#include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 1000 + 5; int vis[maxn]; struct sub{ int lim, score; bool operator < (const sub& p) const { return score > p.score || (score == p.score && lim < p.lim); } }a[maxn]; int main() { int T, n; scanf("%d", &T); while(T--) { memset(vis, 0, sizeof(vis)); scanf("%d", &n); for(int i = 0; i < n; ++i) scanf("%d", &a[i].lim); for(int i = 0; i < n; ++i) scanf("%d", &a[i].score); sort(a, a+n); int ans = 0; for(int i = 0; i < n; ++i) { int flag = 0; for(int j = a[i].lim; j > 0; --j) { if(!vis[j]) { vis[j] = 1; flag = 1; break; } } if(!flag) ans += a[i].score; } printf("%d\n", ans); } return 0; }
如有不当之处欢迎指出!