时间戳

首页 > 解决方案 > Google Jam 2018 参议院疏散

c++ - Google Jam 2018 参议院疏散

问题描述

所以我试图解决 2018 年 Google Code Jam 练习轮的“参议院疏散”问题（无法在标题中放置单词代码：/）（https://codingcompetitions.withgoogle.com/codejam/r​​ound /0000000000000130 /00000000000004c0 )。有关问题的描述，请参阅链接。

我的方法是对政党进行排序，然后总是删除参议员人数最多的政党中的一位参议员。为了仍然知道哪个字母对应哪个数字，我在排序之前将它们配对。然后我创建了一个指针 l，这是每一方在其前拥有最多 senetors 的索引。例如，对于各方 [4,4,4,2,1]，l=2 因为索引为 0,1 和 2 的各方拥有最多的senentors。然后，我总是从索引小于或等于 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

标签： c++algorithm

解决方案

更改代码的两个 while 语句有效。感谢@PaulMcKenziw 指出错误。

while (l<part.size() && part[part.size()-1].first != 0) {
    while (l<part.size()-1 && part[l].first <= part[l+1].first) {

推荐阅读