目录
题面
2515. 开学不开心
描述
什么！大学寒假也有作业！这太令Lux伤心了。。。放假第一天，Lux想到，这才刚放假，作业明天写吧。。。放假第二天，作业什么的，再说吧。。。第三天，明天吧。。。明日复明日，明日何其多。这不，再过几天就开学了，可是Lux的作业还没有写呢。再三思考，Lux只能放弃一部分作业了。可是，放弃哪些作业呢？于是，Lux给每个作业都标上了数值。做完作业，老师会夸奖Lux，那么Lux就会开心。这些数值就是完成作业后Lux能获得的开心值。现在，给你每个作业的deadline和开心值，请你帮助Lux算出最少需要放弃多少开心值。
输入
输入有多组，直到EOF；第一行输入n，表示n个作业；第二行，输入n个整数，表示每个作业的deadline，第三行输入n个整数，表示每个作业的开心值，这些值与第二行的整数一一对应。
3≤n≤100
1≤deadline≤n
0≤happiness≤100
输出
对应每组数据，输出最少放弃的开心值。
输入样例 1 点击复制
3 3 3 3 10 5 1
输出样例 1
0
提示
特别说明：每天只能选择完成一项作业，而且deadline的最大值表示剩下的总天数。
思路
典型的贪心题。
题目要求放弃的happiness（即以下代码中的cost）最小，
1.所以cost越大的task优先级就越高，我们要先安排完成cost大的task；
2.完成task的时间越接近deadline性价比越高（即从deadline开始往前找空位）
重点
第1点我认为是显然成立的。
第2点：为什么要从后往前找？
举例证明：
task： A B
deadline： 6 1
cost： 6 1
如果选择第1天完成A，则B最后无法完成，最后的总cost是1；
如果选择第6天完成A，则B可在第一天完成，最后的总cost是0；
定性证明：
第i天只能选择完成 deadline>=i 的task
假设存在 deadlineA == i 的taskA，deadlineB > i 的taskB
1.第i天选择完成taskA，第deadlineB天完成taskB，最后总cost = 0；
2.第i天选择完成taskB，第deadlineB天无可完成任务，最后总cost = costA；
假设第1~i-1天已安排任务，
task： A1 A2 A3 B
deadline：i+1 i+1 i+1 deadlineB(>i+1)
cost： 6 6 6 7
1.第1,2天选择{A1,A2,A3}其二，第deadlineB天选择B，最后总cost = 6；
2.第1天选择B，第i+1天选择{A1,A2,A3}其一，最后总cost = 12；
代码
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n;
typedef struct {
int deadline;
int cost;
bool status; // true表示已安排
} task;
task a[100];
bool date[10000]; // 记录对应日期是否已安排task,true表示已安排
void input() {
for (int i = 0; i < n; i++) {
scanf("%d", &a[i].deadline);
}
for (int i = 0; i < n; i++) {
scanf("%d", &a[i].cost);
a[i].status = false; // 默认未安排
}
}
int cmp(const void *a, const void *b) {
task *pa = (task *)a;
task *pb = (task *)b;
return (pa->cost < pb->cost) ? 1 : -1; // 按cost降序排序
}
void solve() {
memset(date, false, sizeof(date));
input();
qsort(a, n, sizeof(task), cmp);
int ans = 0; // 总cost
for (int i = 0; i < n; i++) {
for (int j = a[i].deadline; j > 0; j--) {
if (!date[j]) { // 从deadline往前遍历，如果第j天未安排
a[i].status = true; // 标记第i个task已安排
date[j] = true; // 标记第j天已安排
break; // 找到空位，退出循环
}
}
if (!a[i].status) { // 如果遍历结束仍未安排第i个task
ans += a[i].cost;
}
}
printf("%d\n", ans);
return;
}
int main() {
while (scanf("%d", &n) == 1) {
solve();
}
return 0;
}