51Nod 2070 最小罚款 简单题游戏Curren的博客-

1. 题目描述

1.1. Limit

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description

小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者
$m$

m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：

首先，比赛时间分为
$n$

n个时段
$(n≤500)$

(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限
$t_i$

ti​前完成
$(1 le t_i le n)$

(1≤ti​≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费
$m$

m元中扣去一部分钱
$w_i$

wi​，
$w_i$

wi​为自然数，不同的游戏扣去的钱是不一样的。现在你要设计方法，使得你能得到最多的奖励。

1.3. Input

输入共 4 行
第 1 行为
$m$

m ，表示一开始奖励给每位参赛者的钱；
第 2 行为
$n$

n，表示有
$n$

n 个小游戏；
第 3 行有
$n$

n 个数，分别表示游戏 1 到
$n$

n 的规定完成期限；
第 4 行有
$n$

n 个数，分别表示游戏 1 到
$n$

n 不能在规定期限前完成的扣款数。

1.4. Output

输出文件仅 1 行。表示小伟能赢取最多的钱。

1.5. Sample Input

10000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 

1.6. Sample Output

9950 

1.7. Source

51Nod 2070 最小罚款

2. 解读

若存在规定完成期限
$t_i$

ti​相同的任务，则可能会出现惩罚。

若有数字
$t_e$

te​，满足
$1 le t_e < max(t_i)$

1≤te​<max(ti​) 且在所有任务的完成期限中没有出现，那么 对完成期限
$t_i > t_e$

ti​>te​ 的任务
$t_x$

tx​，即使出现了一次重复，也可以使用
$t_e$

te​ 这个时间来完成。

若任务
$t_x$

tx​ 的截止时间
$t_i$

ti​ 前不存在没有出现的数字
$t_e$

te​，或
$t_e$

te​ 被
$t_i$

ti​ 之前出现的重复任务消耗掉了，那么惩罚出现。

惩罚的最优选择方案为，将所有任务按照惩罚金额
$w_i$

wi​从小到大排序，选择第一个符合截止时间
$t_i le t_x$

ti​≤tx​ 条件的任务接受惩罚。即将现有金额
$m$

m 减去
$w_i$

wi​。

对所有规定完成期限
$t_i$

ti​相同的任务进行处理以后，即可求得答案。

3. 代码

#include <iostream> #include <map> #include <math.h> #include <string.h> using namespace std; // 记录最晚完成时间 long long timeList[500]; // 记录惩罚 long long penalty[500]; // 记录出现次数 long long countTime[500]; // 时间到惩罚的映射 multimap<long long, long long> timeToPenalty; // map指针 multimap<long long, long long>::iterator iter; // 将前面轮空的time次数存储起来 long long storage; int main() { long long m, n, maxTime; // 读入m scanf("%lld", &m); // 读入n scanf("%lld", &n); // 初始化数组 memset(timeList, 0, sizeof(timeList)); memset(penalty, 0, sizeof(penalty)); memset(countTime, 0, sizeof(countTime)); // 初始化最大值     maxTime = 0; // 初始化存储     storage = 0; // 存储时间 for (long long i = 0; i < n; i++) { // 读入时间 scanf("%lld", &timeList[i]); // 存储时间的出现次数         countTime[timeList[i]]++; // max         maxTime = max(maxTime, timeList[i]); } // 存储惩罚 for (long long i = 0; i < n; i++) { // 读入惩罚 scanf("%lld", &penalty[i]); // 存入map         timeToPenalty.insert(make_pair(penalty[i], timeList[i])); } // 判断是否有重复元素 for (long long i = 1; i <= maxTime; i++) { // 先消耗存储 if (countTime[i] > 1 && storage > 0) { int countMark = countTime[i] - 1; for (int j = 0; j < countMark; j++) {                 countTime[i]--;                 storage--; if (storage <= 0) { break; } } } // 若有重复时间 if (countTime[i] > 1) { // 将penalty从小到大进行遍历 for (iter = timeToPenalty.begin(); iter != timeToPenalty.end(); iter++) { // 若符合条件 if (iter->second <= i && iter->second != -1) { // 减去penalty                     m -= iter->first; // 将已经减去的penalty清除                     iter->second = -1; // countTime-1                     countTime[i]--; if (countTime[i] <= 1) { // 退出循环 break; } } } } else if (countTime[i] == 0) { // 若有time轮空，存储起来             storage++; } } // 输出 printf("%lld", m); } 

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。