卡牌对弈游戏策略-贪心算法

问题描述
小C最近在玩一种卡牌对弈游戏，双方各持有相同数量的卡牌，每张卡牌都有一个特定的武力值。双方每轮各出一张卡牌，若己方卡牌的武力值大于对方，则该轮取胜。小C具备读心术，能够预知对方的出牌顺序，但需要你帮他设计一个最优策略，来尽可能赢得最多的对弈局数。
每轮对弈中双方各出一张卡牌，游戏结束时需要使用完所有卡牌。你需要输出小C最多能赢得的对弈局数。
例如，当双方手中卡牌的武力值分别为[1，2，31和[1，2，31时，小C可以最多赢得2局。
测试样例
样例1:
输入:n=3，x=[1，2，3]，y=[1，2，3]输出:2
样例2:
输入:n=3，x=[1，3，2]，y=[5，5，5]输出:3
样例3:
输入:n=4，x=[2，4，6，8]，y=[3，3，7，9]输出:3

解题思路

1. 排序：首先，我们可以对小C的卡牌和对手的卡牌进行排序。这样我们可以更容易地找到最优匹配。
2. 贪心策略：从小到大遍历小C的卡牌，对于每一张卡牌，找到对手卡牌中比它小且最大的卡牌进行匹配。如果没有这样的卡牌，则选择对手最小的卡牌进行匹配。

 代码实现：

#include <iostream>
#include <vector>
#include <algorithm>int solution(int n, std::vector<int> x, std::vector<int> y) {// 对小C的卡牌和对手的卡牌进行排序std::sort(x.begin(), x.end());std::sort(y.begin(), y.end());int wins = 0;int j = 0; // 用于追踪对手卡牌的位置// 遍历小C的每一张卡牌for (int i = 0; i < n; ++i) {// 找到对手卡牌中比x[i]小且最大的卡牌while (j < n && y[j] <= x[i]) {j++;}// 如果找到了合适的对手卡牌if (j < n) {wins++;j++; // 使用这张卡牌，移动到下一张}}return wins;
}int main() {std::vector<int> arr1_x = {1, 2, 3};std::vector<int> arr1_y = {1, 2, 3};std::vector<int> arr2_x = {1, 3, 2};std::vector<int> arr2_y = {5, 5, 5};std::vector<int> arr3_x = {2, 4, 6, 8};std::vector<int> arr3_y = {3, 3, 7, 9};std::cout << (solution(3, arr1_x, arr1_y) == 2) << std::endl;std::cout << (solution(3, arr2_x, arr2_y) == 3) << std::endl;std::cout << (solution(4, arr3_x, arr3_y) == 3) << std::endl;return 0;
}