51Nod 2070 最小罚款简单题

文章目录

1. 题目描述
2. 解读
3. 代码

1. 题目描述

1.1. Limit

Time Limit: 1000 ms

Memory Limit: 131072 kB

1.2. Problem Description

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

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

1.3. Input

输入共 4 行
第 1 行为 $m$ ，表示一开始奖励给每位参赛者的钱；
第 2 行为 $n$ ，表示有 $n$ 个小游戏；
第 3 行有 $n$ 个数，分别表示游戏 1 到 $n$ 的规定完成期限；
第 4 行有 $n$ 个数，分别表示游戏 1 到 $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

1.7. Source

51Nod 2070 最小罚款

2. 解读

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

若有数字 $t_{e}$ ，满足 $1 \leq t_{e} < \max (t_{i})$ 且在所有任务的完成期限中没有出现，那么对完成期限 $t_{i} > t_{e}$ 的任务 $t_{x}$ ，即使出现了一次重复，也可以使用 $t_{e}$ 这个时间来完成。

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

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

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

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

51Nod 2070 最小罚款 简单题