Таким образом, я пытался решить проблему «Эвакуация из Сената» в рамках Практического раунда Google Code Jam 2018 года (Невозможно поместить код слова в заголовок: /) (https://codingcompetitions.withgoogle.com/codejam/round/0000000000000130/00000000000004c0). См. Ссылку для описания проблемы.
Мой подход состоял в том, чтобы отсортировать партии, а затем всегда удалять одного сенатора из партии с наибольшим числом сенаторов. Чтобы все еще знать, какая буква соответствует какому номеру, я соединяю их перед сортировкой. Затем я создаю указатель l, то есть индекс, перед которым у каждой партии больше всего старших. Например, для сторон [4,4,4,2,1], l = 2, потому что партии с индексами 0,1 и 2 имеют наибольшее число старших. Затем я всегда удаляю одного старшего из всех сторон с индексом, меньшим или равным l. Чтобы в конце оставался только один сенатор, что означало бы, что у него абсолютное большинство, я всегда удаляю последние две партии с наибольшим сенатором одновременно. Таким образом, для приведенного выше примера я сначала удалил бы сенетора из стороны с индексом 0, а затем одновременно удалил сенатора из стороны 1 и 2.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int T;
cin >> T;
string alph = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
for(int t=0; t<T; t++) {
int N;
cin >> N;
vector<pair<int, char>> part;
for (int n=0; n<N; n++) {
int num;
cin >> num;
part.push_back(pair<int, char>(num, alph[n]));
}
sort(part.begin(), part.end(), greater <>());
cout << "Case #" << t+1 << ": ";
int l = 0;
while (l<part.size()) {
while (l<part.size() && part[l].first <= part[l+1].first) {
l++;
}
for (int i=0; i<=l; i++) {
if (part[i].first > 0) {
part[i].first--;
cout << part[i].second;
if (i+1 != l && part[part.size()-1].first != 0) {
cout << " ";
}
}
}
}
cout << endl;
}
}
Для тестовых случаев все работает отлично , но отправка все равно дает мне неправильный ответ и я просто не могу понять, какой ввод сломает мой код.
Тестовый ввод:
5
2
10 10
3
3 2 2
3
1 1 2
3
2 3 1
5
3 3 3 3 10
Вывод:
Case #1: BA BA BA BA BA BA BA BA BA BA
Case #2: A A CB A CB
Case #3: C C BA
Case #4: B BA B AC
Case #5: E E E E E E E E D C BA E D C BA E D C BA