c++ - 使用c++集的贪心算法错误

Question

我已经创建了一个贪心算法来解决问题(家庭作业)，因为我正在学习 c++ 我想实现同样的事情，但使用 sets .

基本上我们把作业提交到一个在线平台，这个平台作为一些我们不知道的测试用例，然后我们根据它得到一个分数。如果我们通过所有测试用例，我们就有 100%；

问题是这样的

我们有一位 Actor 想要安排与回答关于他的在线问卷调查的粉丝的约会。现在他想选择使问卷中的点数总和最大化并尊重粉丝可用性的粉丝。他一天只能见一个粉丝。

我们有这样的输入:

6
1 1 5  
2 2 4
3 1 2
4 3 1
5 1 6
6 2 2

其中第一行是粉丝数和粉丝数，在每一行中，我们有粉丝id、粉丝可用天数和在线问卷中获得的粉丝积分。我必须打印 Actor 将看到的粉丝的 ID 以及粉丝的综合积分总和。所以对于上述输入，我有以下输出:

2
4
5
11

注意，如果两个粉丝的积分相同，则优先选择ID较小的粉丝。

我首先按调查问卷的分数(降序)对粉丝进行排序，然后按较低的 ID 对粉丝进行排序。读取输入时，我将天数添加到 set 中。我的想法是这样的:

在遍历数据时，我检查可用学习日的粉丝是否在集合中。如果是，则添加此扇形并从集合中删除日期。如果风扇天数不在集合中，则获取 upper_bound 并减少迭代器以将第一天的风扇设置为低于初始日期。当集合为空或我遍历所有风扇时算法停止。

这是我的贪心函数:

void greedy() {
    fan_id.insert(questionnaire_result[0][0]);
    days_available.erase(questionnaire_result[0][1]);
    total_questionaire_sum += questionnaire_result[0][2];

    int i;
    for (i = 1; i < number_of_fans; i++) {
        if (days_available.empty()) {
            break;
        } else if (days_available.count(questionnaire_result[i][1])) {
            fan_id.insert(questionnaire_result[i][0]);
            days_available.erase(questionnaire_result[i][1]);
            total_questionaire_sum += questionnaire_result[i][2];
        } else {
            it = days_available.upper_bound(questionnaire_result[i][1]);
            if (it == days_available.begin()) {
                if (*it < questionnaire_result[i][1]) {
                    fan_id.insert(questionnaire_result[i][0]);
                    days_available.erase(*it);
                    total_questionaire_sum += questionnaire_result[i][2];
                }
            } else if (it == days_available.end()) {
                it--;
                if (*it < questionnaire_result[i][1]) {
                    fan_id.insert(questionnaire_result[i][0]);
                    days_available.erase(*it);
                    total_questionaire_sum += questionnaire_result[i][2];
                }

            } else {
                it--;
                if (*it < questionnaire_result[i][1]) {
                    fan_id.insert(questionnaire_result[i][0]);
                    days_available.erase(*it);
                    total_questionaire_sum += questionnaire_result[i][2];
                }
            }
        }
    }
}

我相信我的问题出在这一行:

it = days_available.upper_bound(questionnaire_result[i][1]);

我已经测试了很多可能性，这在我所有的测试用例中都有效。很遗憾，我们没有平台的测试用例。

有人看到我的代码失败的情况吗？有了这个，我得到了 90% 的分数。

编辑:

正如爱德华指出的那样，我设法解决了这样的问题:

读取输入时添加了这行代码:

max_days = max_days | questionnaire_result[i][1];

然后这样做:

for (int j = 1; j < max_days + 1; j++) {
            days_available.insert(j);
        }

问题解决了

Answer 1

此输入文件将导致程序生成不正确的结果:

2
1 2 6
2 2 5

两个粉丝每天都有空，所以很明显两个粉丝都可以访问，总输出分数应该是 11。但是，您的算法只选择第一个并输出 6 分。