题目： [NOIP2011 普及组] 瑞士轮
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P1309
- 标签：
OI、模拟、递归、排序
思路
- 其基本思路就是按照题目模拟，区分胜者和输者，分区存储，方便下一轮计算，通俗点说就是归并啦，按武力值排序，只不过不是直接排序完，是归并若干次后求值
- 按照题目进行比较，赢者存入a数组，输的存入b，然后通过merge函数合并两个数组存储于s中，这样循环往复，最后按照目标的索引输出即可
- 归并排序：直接调用STL库中函数即可
AC代码
代码语言：javascript复制#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
