Я создал жадный алгоритм для решения проблемы (домашнее задание), и так как я учусь c++
Я хотел бы добиться того же, но используя sets
,
По сути, мы передаем домашнее задание на онлайн-платформу, которая представляет собой несколько тестовых примеров, о которых мы не знаем, и на основании этого мы получаем оценку. Если мы пройдем все тесты, у нас будет 100%;
Проблема в этом.
У нас есть актер, который хочет запланировать встречи с поклонниками, которые ответили на онлайн-анкету о нем. Теперь он хочет выбрать фанатов, которые максимизируют сумму баллов в вопроснике и учитывают доступность фанатов. Он может видеть только одного поклонника в день.
У нас есть такой вклад:
6
1 1 5
2 2 4
3 1 2
4 3 1
5 1 6
6 2 2
Если в первой строке указано количество поклонников, а в каждой строке указывается идентификатор поклонника, число дней, в которые он был доступен, и баллы, полученные в онлайн-вопроснике. Я должен напечатать идентификаторы фанатов, которые увидит актер, и сумму комбинированных баллов фанатов. Таким образом, для вышеуказанного ввода у меня есть следующий вывод:
2
4
5
11
Обратите внимание, что если два вентилятора имеют одинаковые точки, предпочтительным должен быть вентилятор с более низким ID.
Я начал с сортировки поклонников по пунктам анкеты (в порядке убывания), а затем по нижнему идентификатору.
При чтении ввода я добавляю количество дней к set
,
Моя идея была такой:
Перебирая данные, я проверяю, находится ли фанат в доступные учебные дни в 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);
}
Задача решена
Этот входной файл приведет к тому, что программа выдаст неверный результат:
2
1 2 6
2 2 5
Оба вентилятора доступны в любой день, поэтому ясно, что оба вентилятора могут быть посещены, и общий результат должен быть равен 11. Однако ваш алгоритм выбирает только первый и выдает оценку 6.
Других решений пока нет …