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