一个单位时间任务是恰好需要一个单位时间完成的任务。给定一个单位时间任务的有限集S。关于S 的一个时间表用于描述S 中单位时间任务的执行次序。时间表中第1 个任务从时间0 开始执行直至时间1 结束，第2 个任务从时间1 开始执行至时间2 结束，…，第n个任务从时间n-1 开始执行直至时间n结束。
具有截止时间和误时惩罚的单位时间任务时间表问题可描述如下： (1) n 个单位时间任务的集合S={1,2,…,n}； (2) 任务i的截止时间 di ,1≤i≤n,1≤ di ≤n，即要求任务i 在时间di 之前结束； (3) 任务i 的误时惩罚 wi ,1≤i≤n,即任务i 未在时间 di 之前结束将招致 wi 的惩罚； 若按时完成则无惩罚。
任务时间表问题要求确定S 的一个时间表（最优时间表）使得总误时惩罚达到最小。
Description第一行是正整数n，表示任务数。接下来的2行中，每行有n个正整数，分别表示各任务的截止时间和误时惩罚。
Input最小总误时惩罚。
Output 1 2 3 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 Sample Input 1 50 /*贪心算法： 根据罚时的长短进行排序，将罚时时间长的放在前面， 如果相等则按限制时间从小到大排序 用一个vis数组记录在该限制时间是否有任务 如果有就向前面找没有的， 如果还没有那此任务就没法完成， 加上罚时*/ #include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> using namespace std; struct node { int date; int cost; }; bool cmp(node xx, node yy)//排序 { if (xx.cost != yy.cost) return xx.cost > yy.cost; else return xx.date < yy.date; } int main() { int n; node s[10000]; while (cin >> n) { for (int i = 0; i < n; i++) cin >> s[i].date; for (int i = 0; i < n; i++) { cin >> s[i].cost; } sort(s, s + n, cmp); int cnt = 0; int vis[1000] = { 0 }; for (int i = 0; i < n; i++) { if (vis[s[i].date] == 0) { vis[s[i].date] = 1; } else { int flag = 0; for (int j = s[i].date; j >= 1; j--) { if (vis[j] == 0) { vis[j] = 1; flag = 1; break; } } if (flag == 0) { cnt += s[i].cost; } } } cout << cnt << endl; } return 0; }