前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >870. Advantage Shuffle

870. Advantage Shuffle

作者头像
平凡的学生族
发布2019-05-25 09:34:45
3130
发布2019-05-25 09:34:45
举报
文章被收录于专栏:后端技术

870. Advantage Shuffle

思路 用priority_queue<pair<int, int>>解决。使用贪心算法,按数组A从大到小尽可能在数组B中找到匹配的元素即可。就像是“田忌赛马”一样,让A的上等马去应付B的中等马,依次类推,就能有尽可能多的匹配对数。 技巧度:C, 思维绕脑度:C 贪心算法

代码

代码语言:javascript
复制
typedef pair<int, int> mp;

bool operator <(mp &p1, mp &p2){
    return p1.first >= p2.first;
}
class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        priority_queue<mp> q;
        vector<int> res(A.size(), 0);
        stack<mp> st;
        map<int, int> ma;
        map<int, int> mb;
        
        sort(A.begin(), A.end(), greater<int>());
        
        for (int i = 0; i < B.size(); i++)
            q.push({B[i], i});
        
        for (int i = 0; i < A.size(); i++) {
            while(!q.empty() && A[i] <= q.top().first) {
                st.push(q.top());
                q.pop();
            }
            
            if (!q.empty()) {
                auto p = q.top();
                res[p.second] = A[i];
                q.pop();
            }
            else {
                auto p = st.top();
                res[p.second] = A[i];
                st.pop();
            }
        }
        
        
        return res;
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.09.24 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 870. Advantage Shuffle
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档