野生Mouse之间有较严格的等级秩序,每隔一段时间就会举办一场大型的野生Mice比赛。 有2N只编号从0到2N的野生Mouse进行R轮比赛,每轮比赛开始前,以及所有比赛结束后,都会按照每只野生Mice的分数从高到低对选手进行一次排名。约定编号较小的选手排名靠前。 每轮比赛的对阵按【安排与该轮比赛开始前的排名有关:第1名和第2名、第3名和第4名 Mouse之间只进行单纯的力量较量,每场比赛胜者得2分,负者得0分,平手各得1分,也就是说除了首轮以外,其它轮比赛的安排均不能事先确定,而是要取决于野生Mouse在之前比赛中的表现。现给定每个野生Mouse的初始分数及其力量值,试计算在R轮比赛过后,所有野生Mouse的排名。 输入格式: 输入的第一行是两个由空格隔开的正整数N、R,含义如上 第二行是2N个由由空格隔开的非负整数{P},表示每只Mouse的初始分数 第三行是2N个由由空格隔开的非负整数{S},表示每只Mouse的力量值 输出格式: 按排名从小到大输出R轮比赛后2N只野生Mous的编号
时间: 2023-12-18 07:05:14 浏览: 140
这道题目可以使用模拟+快速排序的思路来解决。
首先,我们可以定义结构体来存储每只野生Mouse的编号、分数和力量值:
```cpp
struct Mouse {
int id, score, strength;
bool operator < (const Mouse& t) const {
return score > t.score || (score == t.score && id < t.id);
}
} mouse[N << 1];
```
其中,`id` 表示编号,`score` 表示分数,`strength` 表示力量值。结构体重载了小于号运算符,按照分数从高到低排序,如果分数相同,按照编号从小到大排序。
接着,我们可以读入数据,并对所有野生Mouse按照初始分数进行排序:
```cpp
int n, r;
int main() {
cin >> n >> r;
for (int i = 0; i < (n << 1); i++) {
cin >> mouse[i].score;
mouse[i].id = i;
}
for (int i = 0; i < (n << 1); i++) {
cin >> mouse[i].strength;
}
sort(mouse, mouse + (n << 1));
// 排序后 mouse[0] 为排名第一的野生Mouse
}
```
接下来,我们可以模拟比赛过程。由于每一轮比赛的对阵取决于之前的排名,我们需要在比赛开始前重新对野生Mouse进行排名。
比赛过程中,我们可以使用快速排序来对排名前两位、排名第三位和第四位的野生Mouse进行比赛,更新它们的分数:
```cpp
void simulate() {
for (int i = 0; i < r; i++) {
sort(mouse, mouse + (n << 1));
for (int j = 0; j < n; j++) {
int p1 = j << 1, p2 = p1 | 1;
if (mouse[p1].strength > mouse[p2].strength) {
mouse[p1].score += 2;
} else if (mouse[p1].strength < mouse[p2].strength) {
mouse[p2].score += 2;
} else {
mouse[p1].score += 1;
mouse[p2].score += 1;
}
}
sort(mouse, mouse + (n << 1));
for (int j = 0; j < n; j++) {
int p1 = j << 1 | 1, p2 = p1 - 1;
if (mouse[p1].strength > mouse[p2].strength) {
mouse[p1].score += 2;
} else if (mouse[p1].strength < mouse[p2].strength) {
mouse[p2].score += 2;
} else {
mouse[p1].score += 1;
mouse[p2].score += 1;
}
}
}
}
```
最后,我们可以按照排名从小到大输出所有野生Mouse的编号:
```cpp
int main() {
// ...
simulate();
for (int i = 0; i < (n << 1); i++) {
cout << mouse[i].id + 1 << " ";
}
cout << endl;
return 0;
}
```
完整代码如下:
阅读全文