POJ-3190-分配畜栏

这个题首先，我们需要注意的是它的时间是一秒，其中还包括了你读入数据的时间，因为cin我写的时候没有解除绑定，所以直接超时，我们直接用scanf函数读入50000组数据好了。

然后就是poj交的时候，如果要使用scanf函数和printf函数，就得包括cstdio这个头文件，审查真严格呀。

好了，我们来说说这题吧，这是一道优先队列加上贪心的题目，主要是贪心。

我们首先按照奶牛的挤奶需求，把它们的挤奶时间按照挤奶的开始时间，从早到晚的顺序进行排列。然后我们就开始给它们分配畜栏。

我们认定每个奶牛都有一个序号，我们读入的时候，就给它从1到n-1写入它的序号里面。

分配的过程是这样的：

如果畜栏队列为空，我们就给它直接分配一个畜栏，将总共的畜栏序号++，然后把这头奶牛所放入的畜栏序号，就是当今的畜栏总号，填入pos数组，下标是奶牛的编号。

我们修改这个畜栏的结束时间，改成奶牛挤奶的结束时间，畜栏的序号也改成总的畜栏序号，之后压入优先队列。

如果畜栏队列不为空，就说明此时已经分配了畜栏，如果此时最早结束使用的畜栏，它的结束时间早于这头奶牛挤奶的开始时间，那我们就可以把这头奶牛放入这头畜栏。

我们把这个畜栏弹出优先队列，因为下一次压入之后的结束时间就改变了。

我们修改这个畜栏的结束时间为奶牛挤奶的结束时间，畜栏的序号不变。奶牛 i 的pos数组对应的位置修改成畜栏的序号，将畜栏压入优先队列。

如果最早结束的都不能满足的话，我们就重新给它分配一个畜栏，重复之前的队列为空的流程。

#include <iostream>

#include <cstdio>

#include <queue>

#include <algorithm>

using namespace std;

struct Cow {

	int start,end;

	int num;

	bool operator < (const Cow &b)const {

		return start<b.start;

	}

}cow[50050];

int pos[50050];

struct Stall {

	int end;

	int num;

	bool operator < (const Stall &b)const {

		return end>b.end;

	}

	Stall(int a,int b):end(a),num(b){}

};

int main()

{

	int n;

	scanf("%d",&n);

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

		scanf("%d%d",&cow[i].start,&cow[i].end);

		cow[i].num=i;

	}

	sort(cow,cow+n);

	int total=0;

	priority_queue<Stall>pq;

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

		if (pq.empty()) {

			total++;

			pos[cow[i].num]=total;

			pq.push(Stall(cow[i].end,total));

		}

		else {

			Stall st=pq.top();//结束时间最早的畜栏

			if (st.end<cow[i].start) {

				pq.pop();

				pos[cow[i].num]=st.num;

				pq.push(Stall(cow[i].end,st.num));

			}

			else {

				total++;

				pos[cow[i].num]=total;

				pq.push(Stall(cow[i].end,total));

			}

		}

	}

	printf("%d\n",total);

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

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

	}

	return 0;

}

巴特西

POJ-3190-分配畜栏

最新文章

热门文章