你会得到一个T天的时间线和一个N个分数的列表。您必须将每个分数分配给一天(在 1 到 T 之间)，以便分配的总分数最大化。
虽然有限制。每个分数只能分配给有限天数 X，也可以分配给在特定数字 Y 上或之后发生的天数。
输入采用给定格式：
T
N
分数 X Y(150 4 1表示分数 150 最多可以分配给第 1 天或之后的 4 天)
例如：
T = 10
N = 5
150 4 1
120 4 3
200 2 7
100 10 5
50 5 1
注意 = 2 分数可以具有相同的值。每天最多可以分配 1 个分数。
上述示例的最佳结果为：150 150 150 150 120 120 200 200 120 120。
我试过什么：
我根据分数对列表进行排序，然后开始首先分配最高分数。
在上面的例子中，我将从 200 开始，并将其分配给 7 天和 8 天。
同样，我会将下一个最高分分配给 150 到 1、2、3 和 4 天。 等等...
但这需要 O(N * T) 时间。N 用于迭代分数列表，T 用于在时间线上检查和分配分数(在最坏的情况下)。
目标是最大化和计算最终分数。
有没有更优雅的方法可以做到这一点？就像甚至没有分配分数，从而取消了 O(N * T) 的 T 部分。
我为您的算法编写了一个非常简单的实现：
#include <vector>
#include <algorithm>
#include <array>
constexpr int T = 10;
struct Item {
int score;
int count;
int min;
};
std::array<Item, 5> input={{
{150, 4, 1},
{120, 4, 3},
{200, 2, 7},
{100, 10, 5},
{50, 5, 1}
}};
std::array<bool, T> days{};
int main() {
// preprocess input
std::sort(input.begin(), input.end(), [](auto l, auto r) {return l.score > r.score; });
int totalScore = 0;
int lastFreeDay = T - 1;
[&] {
for (auto spec : input) {
// scan forward to find open spots for the scores
for (int pos = spec.min-1; spec.count && pos < lastFreeDay; ++pos) {
if (!days[pos]) {
days[pos] = true;
totalScore += spec.score;
spec.count--;
}
}
// we weren't able to assign all scores of this entry,
// so every day after spec.min has already a score assigned to it.
// lets scan backward and see where the last free one is
if (spec.count > 0) {
lastFreeDay = spec.min;
while (days[lastFreeDay]) {
if (--lastFreeDay == -1) {
return;
}
}
}
}
}();
return totalScore;
}
我不确定确切的算法复杂性是多少，但您可以看到两件事：
- 一开始，碰撞很少，所以内部循环实际上并不依赖于
T，所以它的行为更像O(N*k)(其中k是你可以分配特定分数的平均次数)。 - 即使 N 增长得非常大，也不是所有分数都可以实际处理，因为算法可以提前终止，并将最新的空闲日与可以分配的最早 da 进行比较。
当然，你可以创建一个最坏情况的输入，其中你有内循环的 T*(T+1)/2 次传递(对于 N == T 和 k = 1 和 min_i = 1)，但我的直觉是平均而言，它比 O(N*T) 好得多，或者至少有一个非常小的常数(实际上， 排序可能是主导因素)。
长话短说：我非常有信心你的算法实际上适用于实践，并且可能会通过Prune建议的更智能的数据结构进一步改进。
如果您维护一个可用间隔表，我相信您可以将其保持在O(N + T)。 不要每次都穿过整个长度T;只需检查打开间隔列表，并从包含输入行Y值的第一个可用间隔开始。 在这个"开放"列表中不会有超过 N/2 个间隔，散列或二叉搜索都可以控制复杂性。