克罗地亚议会选举 - 党派代表分配算法

这道题目可以使用贪心算法来解决。首先，计算每个党派的得票率，即党派获得的票数除以总投票人数。然后，按照得票率从高到低对党派进行排序。接下来，按照党派得票率从高到低依次选取代表，直到选满14位代表或者党派已经没有剩余的候选人为止。\n\n具体实现如下：\n\n1.读入投票人总数X和党派数N；\n2.定义一个结构体Party，包含党派标识符和得票率；\n3.定义一个vector<Party> parties，用于存储每个党派的信息；\n4.循环N次，读入党派标识符和获得的票数G，计算得票率并将党派信息存入parties中；\n5.按照得票率从高到低对parties进行排序；\n6.定义一个vector<pair<char, int>> representatives，用于存储选出的代表，其中pair的第一个元素为党派标识符，第二个元素为代表人数；\n7.循环遍历parties，按照得票率从高到低选取代表，直到选满14位代表或者党派已经没有剩余的候选人为止；\n8.按照党派标识符的字母顺序对representatives进行排序；\n9.循环遍历representatives，输出每个党派的标识符和选出的议员人数。\n\n代码实现如下：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <algorithm>\nusing namespace std;\n\nstruct Party {\n char identifier;\n double voteRate;\n};\n\nbool cmp(Party a, Party b) {\n return a.voteRate > b.voteRate;\n}\n\nint main() {\n int X, N;\n cin >> X >> N;\n \n vector<Party> parties;\n for (int i = 0; i < N; i++) {\n char identifier;\n int G;\n cin >> identifier >> G;\n \n Party party;\n party.identifier = identifier;\n party.voteRate = (double)G / X;\n \n parties.push_back(party);\n }\n \n sort(parties.begin(), parties.end(), cmp);\n \n vector<pair<char, int>> representatives;\n int count = 0;\n for (int i = 0; i < parties.size(); i++) {\n int numRepresentatives = parties[i].voteRate * 14;\n if (numRepresentatives == 0) {\n break;\n }\n \n if (count + numRepresentatives <= 14) {\n representatives.push_back(make_pair(parties[i].identifier, numRepresentatives));\n count += numRepresentatives;\n } else {\n representatives.push_back(make_pair(parties[i].identifier, 14 - count));\n break;\n }\n }\n \n sort(representatives.begin(), representatives.end());\n \n for (int i = 0; i < representatives.size(); i++) {\n cout << representatives[i].first << " " << representatives[i].second << endl;\n }\n \n return 0;\n}\n\n\n时间复杂度分析：首先，读入投票人总数X和党派数N的时间复杂度为O(1)。然后，循环N次读入党派信息的时间复杂度为O(N)。接下来，对parties进行排序的时间复杂度为O(NlogN)。最后，循环遍历parties和representatives输出结果的时间复杂度为O(N)。因此，总的时间复杂度为O(NlogN)。\n\n空间复杂度分析：除了输入输出外，额外使用了一个vector parties和一个vector representatives来存储党派信息和选出的代表，所以空间复杂度为O(N)。