c++ - Bank Kattis 问题的算法正确性

Question

This是我指的问题。快速总结:

输入:一个整数时间T；银行关闭的时间(以分钟为单位)和一组 c 和 t 表示此人携带的现金数量(整数)和从现在开始的时间(以分钟为单位)如果没有送达，此人将离开。服务一个人需要一分钟，您必须最迟在 t 时间开始服务一个人。

输出:在关闭时间内可以收取的最大金额。

我的方法是:将所有人放在一张将金钱与时间对应起来的 map 上。我按钱对这张 map 进行排序。然后我做了一个类似队列的结构，我把钱最多的人放在尽可能远的地方。如果该位置已被占用，那么我将继续前进，直到找到一个位置。如果我不能，那么我就不会添加这个人。

下面是我的辅助函数，用于确定我是否可以插入一个人。

// returns index where we can insert, otherwise -1
int canInsert(bool* queue, int timeToInsert) {
    if (!queue[timeToInsert]) {
        return timeToInsert;
    } else {
        int index = timeToInsert-1;
        while (index >= 0) {
            if (!queue[index]) {
                return index;
            } else {
                index--;
            }
        }
        return -1;
    }
}

这里是主要的驱动函数:

// moneyToTime is a map that maps a person's money to the time value
int Bank(int T, map<int, int> moneyToTime) {
    int answer = 0;
    bool queue[47] = {0};
    for (map<int,int>::reverse_iterator i = moneyToTime.rbegin(); i != moneyToTime.rend(); i++) {
        if (T > 0) {
            // try to insert. If we can, then add to sum. Otherwise, don't.
            int potentialIndex = canInsert(queue, i->second);
            if (potentialIndex != -1) {
                queue[potentialIndex] = 1;
                answer += i->first;
                T--;
            }
        } else {
            break;
        }
    }
    return answer;
}

从逻辑上讲，这对我来说很有意义，而且它几乎通过了所有测试用例。有一对失败了；我看不出它们是什么。测试用例错误实际上表明错误的答案，而不是糟糕的运行时错误。有人可以帮我看看我的方法中的谬误吗？

Answer 1

您没有展示如何构建 moneyToTime但无论如何它看起来像map<int, int>是错误的类型。想象一下，你有很多人拥有相同数量的金钱和不同的时间。那么您将如何在您的 moneyToTime 中表示？ ？

如果我的理论是正确的，像这样的例子应该会破坏你的解决方案:

3 3
2000 2
2000 1
500 2

显然最好的总和是 4000 = 2000 + 2000。我怀疑你只能得到 2500。