田忌赛马（C++）

2024/10/27 16:20:09 来源：https://blog.csdn.net/lim6ere/article/details/141993730 浏览: 次关键词：田忌赛马（C++）

文章目录

前言
一、2418. 按身高排序
二、870. 优势洗牌
- 算法原理
- 代码编写
总结

前言

一、2418. 按身高排序

2418. 按身高排序

在介绍田忌赛马这道题目之前，我们需要先对这个道题目进行一定的掌握。

我们解决这道题目有很多方法，我们这里仅仅介绍一种最常用的。
题目中我们并不想排序后改变原始位置，我们可以用下面方法：
🌟1.创建一个数组下标
🌟2.对数组下标通过重写比较方法进行重新排序
🌟根据重新排序后的结果，找到原数组的信息。

class Solution {
public:vector<string> sortPeople(vector<string>& names, vector<int>& heights) {//1.创建一个数组下标int n=heights.size();vector<int>index(n);for(int i=0;i<n;i++){index[i]=i;}//2.对数组下标进行排序，重写比较方法sort(index.begin(),index.end(),[&](int i,int j){//按照身高降序排列return heights[i]>heights[j];});//3.根据数组下标排序后结果，找到原数组信息vector<string>ret;for(auto&e:index){ret.push_back(names[e]);}return ret;}
};

二、870. 优势洗牌

870. 优势洗牌

算法原理

⽥忌赛⻢没听过的⾃⾏百度，这⾥讲⼀下⽥忌赛⻢背后的博弈决策，从三匹⻢拓展到 n 匹⻢之间
博弈的最优策略。
⽥忌：下等⻢中等⻢上等⻢
⻬王：下等⻢中等⻢上等⻢
比特就业课
a. ⽥忌的下等⻢ pk 不过⻬王的下等⻢，因此把这匹⻢丢去消耗⼀个⻬王的最强战⻢！
b. 接下来选择中等⻢ pk ⻬王的下等⻢，勉强获胜；
c. 最后⽤上等⻢ pk ⻬王的中等⻢，勉强获胜。

我们的策略：
🌟 先把两个数组进行升序排列
🌟 两个数组的最小值依次比较，如果nums1的最小值比nums2的最小值还小或者两个相等，我们就用他拼掉nums2中的最大值，获得利益最大化。
🌟 如果num1的最小值比nums2最小值大，就跟这个值比较，肯定能获胜
🌟 由于我们需要返回优势最大的数组，所以nums2的顺序不能动，但是我们又想用这个进行排序，就需要用到我们上面的方法了。

代码编写

class Solution {
public:vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {//排序int n=nums1.size();sort(nums1.begin(),nums1.end());vector<int>index(n);for(int i=0;i<n;i++) index[i]=i;sort(index.begin(),index.end(),[&](int i,int j){return nums2[i]<nums2[j];});//田忌赛马vector<int>ret(n);int left=0;int right=n-1;for(auto&e:nums1){if(e<=nums2[index[left]]) ret[index[right--]]=e;else ret[index[left++]]=e;}return ret;}};