【第51题】 [NOIP2011 普及组] 瑞士轮，一道归并排序题

小码匠

发布于 2023-08-31 14:52:50

2150

发布于 2023-08-31 14:52:50

文章被收录于专栏：小码匠和老码农

题目： [NOIP2011 普及组] 瑞士轮

题目原文请移步下面的链接

https://www.luogu.com.cn/problem/P1309
标签：OI、模拟、递归、排序

思路

其基本思路就是按照题目模拟，区分胜者和输者，分区存储，方便下一轮计算，通俗点说就是归并啦，按武力值排序，只不过不是直接排序完，是归并若干次后求值
按照题目进行比较，赢者存入a数组，输的存入b，然后通过merge函数合并两个数组存储于s中，这样循环往复，最后按照目标的索引输出即可
归并排序：直接调用STL库中函数即可

AC代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n';

void best_coder();
void happy_coder();

int main() {
    // 小码匠
    best_coder();

    // 最优解
    //happy_coder();
    return 0;
}

int cmp(pair<int, int> a, pair<int, int> b) {
    if (a.first == b.first) {
        return a.second < b.second;
    }
    return a.first > b.first;
}

void best_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, r, q;
    cin >> n >> r >> q;
    n *= 2;
    vector<pair<int, int>> s(n);
    vector<int> w(n);
    vector<pair<int, int>> a(n / 2);
    vector<pair<int, int>> b(n / 2);

    for (int i = 0; i < n; ++i) {
        cin >> s[i].first;
        s[i].second = i;
    }
    for (int i = 0; i < n; ++i) {
        cin >> w[i];
    }
    sort(s.begin(), s.end(), cmp);
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < n; j += 2) {
            if (w[s[j].second] > w[s[j + 1].second]) {
                ++s[j].first;
                a[j / 2] = s[j];
                b[j / 2] = s[j + 1];
            } else {
                ++s[j + 1].first;
                a[j / 2] = s[j + 1];
                b[j / 2] = s[j];
            }
        }
        merge(a.begin(), a.end(), b.begin(), b.end(), s.begin(), cmp);
    }
    cout << s[q - 1].second + 1;
}

void happy_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

END

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-06-26，如有侵权请联系 cloudcommunity@tencent.com 删除

存储