Skip to content

51Nod 2070 最小罚款#

目录#

1. 题目描述#

1.1. Limit#

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description#

小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：

首先，比赛时间分为个时段，它又给出了很多小游戏，每个小游戏都必须在规定期限前完成。如果一个游戏没能在规定期限前完成，则要从奖励费元中扣去一部分钱，为自然数，不同的游戏扣去的钱是不一样的。现在你要设计方法，使得你能得到最多的奖励。

1.3. Input#

输入共 4 行 第 1 行为 ，表示一开始奖励给每位参赛者的钱； 第 2 行为 ，表示有 个小游戏； 第 3 行有 个数，分别表示游戏 1 到 的规定完成期限； 第 4 行有 个数，分别表示游戏 1 到 不能在规定期限前完成的扣款数。

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. 解读#

若存在规定完成期限 相同的任务，则可能会出现惩罚。

若有数字，满足 且在所有任务的完成期限中没有出现，那么 对完成期限 的任务 ，即使出现了一次重复，也可以使用 这个时间来完成。

若任务 的截止时间 前不存在没有出现的数字，或 被 之前出现的重复任务消耗掉了，那么惩罚出现。

惩罚的最优选择方案为，将所有任务按照惩罚金额从小到大排序，选择第一个符合截止时间 条件的任务接受惩罚。即将现有金额 减去 。

对所有规定完成期限 相同的任务进行处理以后，即可求得答案。

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，有问题欢迎通过邮箱交流。

Back to top