红蓝对战c++
时间: 2023-06-29 18:08:08 浏览: 51
红蓝对战是一种经典的算法竞赛题目,通常在 ACM 竞赛中出现。下面给出一个简单的 C++ 实现:
```cpp
#include <iostream>
using namespace std;
const int MAXN = 1005;
int red[MAXN], blue[MAXN];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> red[i];
}
for (int i = 0; i < m; i++) {
cin >> blue[i];
}
int i = 0, j = 0, ans = 0;
while (i < n && j < m) {
if (red[i] < blue[j]) {
i++;
} else if (red[i] > blue[j]) {
j++;
} else {
ans++;
i++;
j++;
}
}
cout << ans << endl;
return 0;
}
```
其中,`red` 数组存储红队的数值,`blue` 数组存储蓝队的数值。我们使用两个指针 `i` 和 `j` 分别指向红队和蓝队的当前比较位置,如果 `red[i] < blue[j]`,则红队的当前数值小于蓝队的当前数值,红队指针 `i` 右移一位;如果 `red[i] > blue[j]`,则蓝队的当前数值小于红队的当前数值,蓝队指针 `j` 右移一位;如果 `red[i] == blue[j]`,则两队当前数值相等,答案加一,并将两个指针都右移一位。最终,输出答案即可。
需要注意的是,红队和蓝队的数值都是按照升序排列的,因此我们可以使用上述的双指针算法,时间复杂度为 O(n+m)。