洛谷 [P2859] 摊位预定

贪心

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int MAXN = 50005;

int init() {

	int rv = 0, fh = 1;

	char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') fh = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		rv = (rv<<1) + (rv<<3) + c - '0';

		c = getchar();

	}

	return fh * rv;

}

struct cow{

	int s, t, num;

	bool operator < (const cow & b) const {

		return s < b.s;

	}

}a[MAXN];

struct ket{

	int num, tim;

	bool operator < (const ket & b) const {

		return tim > b.tim;

	}

};

int n, ans[MAXN], cnt;

priority_queue <ket> q;

int main() {

	n = init();

	for(int i = 1; i <= n; i++) {

		cin >> a[i].s >> a[i].t;

		a[i].num = i;

	}

	sort(a + 1, a + n + 1);

	q.push({1, a[1].t});

	ans[a[1].num] = 1;

	cnt++;

	for(int i = 2; i <= n; i++) {

		if(q.top().tim < a[i].s) {

			ket t;

			t = q.top();

			q.pop();

			t.tim = a[i].t;

			q.push(t);

			ans[a[i].num] = t.num;

		}else {

			cnt++;

			ket t;

			t.num = cnt;

			t.tim = a[i].t;

			q.push(t);

			ans[a[i].num] = cnt;

		}

	}

	cout << cnt << endl;

	for(int i = 1;i <= n; i++) {

		printf("%d\n", ans[i]);

	}

	return 0;

}
巴特西

洛谷 [P2859] 摊位预定

贪心

最新文章

热门文章
