С . Задача "Выборы в США" Выборы в США
Как известно, в США президент выбирается не прямым голосованием, а путём двухуровневого голосования. Сначала проводятся выборы в каждом штате, и определяется победитель выборов в данном штате. Затем проводятся государственные выборы: на этих выборах каждый штат имеет определённое число голосов — число выборщиков от этого штата. На практике все выборщики от штата голосуют в соответствии с результатами голосования внутри штата, то есть на заключительной стадии выборов в голосовании участвуют штаты, имеющие различное число голосов.
На этот раз вам известно число выборщиков от каждого штата США и результаты голосования каждого гражданина США (а также в каком штате проживает данный гражданин).
Вам необходимо подвести результаты голосования: сначала определить результаты голосования в каждом штате и определить, за кого из кандидатов отданы голоса выборщиков данного штата. Далее необходимо подвести результаты голосования выборщиков по всем штатам.
Входные данные
Первая строка входных данных содержит количество штатов в США N (1≤N≤100000). Далее идёт N строк, описывающих штаты США, каждая строка состоит из названия штата и числа выборщиков от этого штата. На следующей строке задано число M (1≤M≤100000)— количество проголосовавших на выборах. В следующих M строках идут записи результатов голосования по каждому из участников голосования. Одна строка соответствует одному избирателю. Записи имеют следующий вид: название штата, имя кандидата, за которого проголосовал данный избиратель. Названия штатов и имена кандидатов не содержат пробелов.
Выходные данные
Выведите список кандидатов, упорядоченный по убыванию числа голосов выборщиков, полученных за данного кандидата, а при равенстве числа голосов выборщиков — в лексикографическом порядке. После имени кандидата выведите число набранных им голосов.
Если в каком-либо штате два или более кандидатов набрали одинаковое число голосов, то все голоса выборщиков этого штата получает наименьший в лексикографическом порядке кандидат из числа победителей в этом штате.
Гарантируется, что в каждом штате проголосовал хотя бы один избиратель.
Примечание к примерам тестов
В Florida 2 избирателя голосует за Gore и три избирателя за Bush, поэтому 25 голосов выборщиков от Florida получает Bush. В Pennsylvania побеждает Gore (5 голосов против 1), поэтому Gore получает 23 голоса выборщиков от Pennsylvania.
В Florida побеждает Gore (5 голосов выборщиков), в Alaska — Bush (2 голоса выборщиков). В Pennsylvania два кандидата набрали наибольшее число голосов (по 1), поэтому 4 голоса выборщиков от этого штата получает Clinton, т.к. он идет раньше в лексикографическом порядке.
Примеры
Ввод
Вывод
2
Florida 25
Pennsylvania 23
11
Florida Gore
Pennsylvania Gore
Florida Bush
Pennsylvania Gore
Pennsylvania Bush
Florida Gore
Pennsylvania Gore
Florida Bush
Pennsylvania Gore
Florida Bush
Pennsylvania Gore
Bush 25
Gore 23
3
Florida 5
Pennsylvania 4
Alaska 3
4
Florida Gore
Pennsylvania Obama
Pennsylvania Clinton
Alaska Bush
Gore 5
Clinton 4
Bush 3
Obama 0
Опубликовал решение на PasteBin и тут, поскольку суда криво копируются символы таба, и потом нельзя нормально скопировать код. https://pastebin.com/kWSChLsh
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct State {
vector<pair<string, int>> candidates; // кандидаты в этом штате
string state; // название штата
int weight; // "вес" штата
State(string state = " ", int weight = 0) : state(state), weight(weight) {
}
void vote(string candidate) { // принимаем голос избирателя
if (candidates.size() == 0) {
candidates.push_back({ candidate, 1 });
return;
}
for (int i = 0; i < candidates.size(); ++i) {
if (candidates[i].first == candidate) {
++candidates[i].second;
break;
}
else if (i == candidates.size() - 1) {
candidates.push_back({ candidate, 0 });
}
}
}
string getResultOfElections() {
if (candidates.size() == 1) {
return candidates[0].first;
}
sort(candidates.begin(), candidates.end(), // сортировка по голосам
[](pair<string, int>& a, pair<string, int>& b) {
return (a.second > b.second);
});
int last = -1;
for (int i = 1; i < candidates.size(); ++i) { // убираем проигравших
if (candidates[i].second != candidates[0].second) {
last = i;
break;
}
}
if (last != -1)
candidates.erase(candidates.begin() + last);
sort(candidates.begin(), candidates.end(), // лексографическая сортировка
[](pair<string, int>& a, pair<string, int>& b) {
return strcmp(a.first.c_str(), b.first.c_str()) < 0;
});
return candidates[0].first; // победитель
}
};
int main() {
setlocale(LC_ALL, "Russian");
cout << "Введите количество штатов: ";
vector<State> states;
int nOfStates = 0;
cin >> nOfStates;
cin.ignore();
cout << "Введите данные о состоянии штатов в формате Название_штата Значимость_Штата: ";
for (int i = 1; i <= nOfStates; ++i) {
string input, buffer, name, weight;
getline(cin, input);
name = input.substr(0, input.find(' '));
weight = input.substr(input.find(' '));
states.push_back(State(name, stoi(weight)));
}
cout << "Количество голосов: ";
int nOfVotes = 0;
cin >> nOfVotes;
cin.ignore();
cout << "Данные о голосах в формате Штат Кандидат: ";
for (int i = 0; i < nOfVotes; ++i) {
string input, state, candidate;
getline(cin, input);
state = input.substr(0, input.find(' '));
candidate = input.substr(input.find(' ') + 1);
for (int j = 0; j < nOfStates; ++j) {
if (states[j].state == state) {
states[j].vote(candidate);
}
}
}
vector<pair<string, int>> winners;
for (int i = 0; i < states.size(); ++i) {
string result = states[i].getResultOfElections();
if (winners.size() == 0) {
winners.push_back({ result, states[i].weight });
continue;
}
for (int j = 0; j < winners.size(); ++j) {
if (winners[j].first == result) {
winners[j].second += states[i].weight;
break;
}
else if (j == winners.size() - 1) {
winners.push_back({ result, 0 });
}
}
}
cout << endl;
for (int i = 0; i < winners.size(); ++i) {
cout << winners[i].first << " " << winners[i].second << endl;
}
}