首页 > 其他 > 详细

优先队列重载<运算符

时间:2018-05-06 23:49:26      阅读:315      评论:0      收藏:0      [点我收藏+]

https://vjudge.net/problem/POJ-3190

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
struct Node{
    int x, y;
    int id;
    bool operator<(const Node &a)const{
        return y > a.y;
    }
}node[50010];
int n, maxm = -INF, b[50010];
bool cmp(const Node a, const Node b)
{
    if(a.x != b.x)
        return a.x<b.x;
    return a.y<b.y;
}
int main()
{
    scanf("%d", &n); 
    int ans = 1;
    for(int i = 0; i < n; i++){
        scanf("%d%d", &node[i].x, &node[i].y);
        node[i].id=i+1;
    }
    sort(node, node+n, cmp);
    priority_queue<Node> q;
    q.push(node[0]);
    b[node[0].id] = ans;
    for(int i = 1; i < n; i++){
        Node t = q.top();
        if(node[i].x <= t.y){
            q.push(node[i]);
            ans++;
            b[node[i].id] = ans;
            //maxm = max(maxm, ans);
        }
        else if(node[i].x > t.y){
            q.pop();
            q.push(node[i]);
            b[node[i].id] = b[t.id];
            //cout << b[t.id] << "t";
        }
    }
    printf("%d\n", ans);
    for(int i = 1; i <= n; i++){
        printf("%d\n", b[i]);
    }
    
    return 0;
} 

 

优先队列重载<运算符

原文:https://www.cnblogs.com/Surprisezang/p/9000373.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!