poj 3190

大佬教程收集整理的这篇文章主要介绍了poj 3190，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

// poj 3190.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <queue>
#include <vector>
//#include <unordered_map>
#include <algorithm>

using namespace std;


/*
Input
Line 1: A single Integer, N
Lines 2..N+1: Line i+1 describes cow i's milking interval with two space-separated Integers.
Output
Line 1: The minimum number of stalls the barn must have.
Lines 2..N+1: Line i+1 describes the stall to 
which cow i will be assigned for her milking period.
Sample Input

5
1 10
2 4
3 6
5 8
4 7
Sample Output

4
1
2
3
2
4
*/


struct COW {
	int start;
	int end;
	int num;
	int stall;
};


struct cmp {
	bool operator()(struct COW& x, struct COW& y)
	{
		return  x.end > y.end;
	}
};

priority_queue<struct COW, vector<struct COW>, cmp> q;    //定义方法
int n;
 

bool cmp_COW(const struct COW& a, const struct COW& b) {
	return a.start < b.start;
}

struct COW mm[1000010];

int main()
{
	cin >> n;
	vector<struct COW> arr;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;

		struct COW t; t.start = a; t.end = b; t.num = i;
		arr.push_BACk(t);
	}

	sort(arr.begin(), arr.end(),cmp_COW);

	int ans = 0;
	//unordered_map<int, struct COW> mm;

	for (int i = 0; i < arr.size(); i++) {
		if (q.empty() || q.top().end >= arr[i].start) {
			ans++;
			arr[i].stall = ans;
			q.push(arr[i]);
		}
		else {
			struct COW t = q.top();
			mm[t.num] = t;
			q.pop();
			arr[i].stall = t.stall;
			q.push(arr[i]);
		}
	}
	
	cout << ans << endl;

	while (!q.empty()) {
		struct COW t = q.top();
		mm[t.num] = t;
		q.pop();
	}

	for (int i = 0; i < n; i++) {
		cout << mm[i].stall << endl;
	}
	
	return 0;
}

大佬总结

以上是大佬教程为你收集整理的poj 3190全部内容，希望文章能够帮你解决poj 3190所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。