870. Advantage Shuffle

哈哈哈, 這個題目看完, 在看討論只要是跟華人文化有關的, 大家都知道這就是孫子兵法著名的 田忌賽馬,

故事大家應該都很耳熟能詳了, 如果不熟可以谷歌一下

簡單來說, 當我發現如果這匹馬不管怎樣都贏不了對面的馬, 或是最多持平, 那我們就讓他去輸給對方最強的馬, 用最爛的旗子換取對方最大的輸出

這邊先把A 陣列的馬兒們排序一下, 好理順我們得戰力, 然後根據B的每隻馬給出應對

若Ｂ的馬我們不管怎樣都贏不了, 那我們就派出A這邊最弱的馬

若有可以贏的馬, 我們就從A找upper bound去打就行了

順便練一下multiset的用法

multiset跟set最大的差別應該還是在mutliset 允許重複, set不允許

class Solution {
public:
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
      vector<int> res;
      multiset<int> st(A.begin(), A.end());
      for(int i = 0; i < B.size();i++){
        auto it = (*st.rbegin() <= B[i])? st.begin(): st.upper_bound(B[i]);
        res.push_back(*it);
        st.erase(it);
      }
      return res;
    }
};

但如果對multiset不熟悉的話, 我們也可以用priority_queue

我們可以先將我們的馬給排序一下,

然後把B的馬依照戰力由大到小排好, 另外要紀錄index

然後每匹馬都拿出來比較, 理論上, B的最大戰力如果A最好的戰力沒辦法打, 那我們就派出A最爛的馬去送頭

道理上是一樣的

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
      vector<int> res(A.size());
      sort(A.begin(), A.end());
      priority_queue<pair<int, int>> q;
      for(int i = 0; i < B.size();i++){
        q.push({B[i], i});
      }
      int l = 0;
      int r = A.size() - 1;
      while(!q.empty()){
        int cur_val = q.top().first;
        int cur_idx = q.top().second;
        q.pop();
        if(cur_val < A[r]){
          res[cur_idx] = A[r];
          r--;
        }else{
          res[cur_idx] = A[l];
          l++;
        }
      }
      return res;
    }
};