gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:54:50 26 4
gpt4 key购买 nike

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

输入:一个整数时间T;银行关闭的时间(以分钟为单位)和一组 ct 表示此人携带的现金数量(整数)和从现在开始的时间(以分钟为单位)如果没有送达,此人将离开。服务一个人需要一分钟,您必须最迟在 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;
}

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

最佳答案

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

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

3 3
2000 2
2000 1
500 2

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

关于c++ - Bank Kattis 问题的算法正确性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54300139/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com