cpp题目描述1212 月初克罗地亚举行了国家议会选举。克罗地亚分为 10 个选举地区。每个地区我们要选出 1414 名议会代表。在该地区中每个投票人都会为自己的党派投上一票。投票后使用 �′�����D ′ Hondt 的方式选出 这 1414 名议会代表。选举的方式如下：首先我们选出票数至少占投票人总数 55 的各党派。然后将每个党派的投票数除 以 11 到 1414 中的每个数。通过这种方式

这道题目可以使用贪心算法来解决。首先，计算每个党派的得票率，即党派获得的票数除以总投票人数。然后，按照得票率从高到低对党派进行排序。接下来，按照党派得票率从高到低依次选取代表，直到选满14位代表或者党派已经没有剩余的候选人为止。

具体实现如下：

1.读入投票人总数X和党派数N； 2.定义一个结构体Party，包含党派标识符和得票率； 3.定义一个vector parties，用于存储每个党派的信息； 4.循环N次，读入党派标识符和获得的票数G，计算得票率并将党派信息存入parties中； 5.按照得票率从高到低对parties进行排序； 6.定义一个vector<pair<char, int>> representatives，用于存储选出的代表，其中pair的第一个元素为党派标识符，第二个元素为代表人数； 7.循环遍历parties，按照得票率从高到低选取代表，直到选满14位代表或者党派已经没有剩余的候选人为止； 8.按照党派标识符的字母顺序对representatives进行排序； 9.循环遍历representatives，输出每个党派的标识符和选出的议员人数。

代码实现如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Party {
    char identifier;
    double voteRate;
};

bool cmp(Party a, Party b) {
    return a.voteRate > b.voteRate;
}

int main() {
    int X, N;
    cin >> X >> N;
    
    vector<Party> parties;
    for (int i = 0; i < N; i++) {
        char identifier;
        int G;
        cin >> identifier >> G;
        
        Party party;
        party.identifier = identifier;
        party.voteRate = (double)G / X;
        
        parties.push_back(party);
    }
    
    sort(parties.begin(), parties.end(), cmp);
    
    vector<pair<char, int>> representatives;
    int count = 0;
    for (int i = 0; i < parties.size(); i++) {
        int numRepresentatives = parties[i].voteRate * 14;
        if (numRepresentatives == 0) {
            break;
        }
        
        if (count + numRepresentatives <= 14) {
            representatives.push_back(make_pair(parties[i].identifier, numRepresentatives));
            count += numRepresentatives;
        } else {
            representatives.push_back(make_pair(parties[i].identifier, 14 - count));
            break;
        }
    }
    
    sort(representatives.begin(), representatives.end());
    
    for (int i = 0; i < representatives.size(); i++) {
        cout << representatives[i].first << " " << representatives[i].second << endl;
    }
    
    return 0;
}

时间复杂度分析：首先，读入投票人总数X和党派数N的时间复杂度为O(1)。然后，循环N次读入党派信息的时间复杂度为O(N)。接下来，对parties进行排序的时间复杂度为O(NlogN)。最后，循环遍历parties和representatives输出结果的时间复杂度为O(N)。因此，总的时间复杂度为O(NlogN)。

空间复杂度分析：除了输入输出外，额外使用了一个vector parties和一个vector representatives来存储党派信息和选出的代表，所以空间复杂度为O(N)