hdu 5360 Hiking(优先队列+贪心)

题目：http://acm.hdu.edu.cn/showproblem.php?

pid=5360

题意：beta有n个朋友,beta要邀请他的朋友go hiking,已知每一个朋友的理想人数[L,R](现有L~R个人准备去,那么这个朋友就去)。

求最多有多少人去。

及beta邀请朋友的顺序。

分析：每次邀请人的最优解就是：选会去的人里面R最小的那个人。

代码实现的话,cur代表已经准备go hiking的人数,每次将全部L<=cur的人放进优先队列,选出R最小的那个。

假设队列为空,那么剩下的全部人将不会去,假设先出的那个人的[L,R]不满足条件,那么这个人以后也不会去go
hiking,所以还是将他选出,仅仅是去go hiking的人数不增。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int maxn = 1e5+5;

struct node

{

	int L,R,id;

	bool operator < (const node &t) const

	{

		return R>t.R;

	}

}s[maxn];

bool cmp(node a,node b)

{

	if(a.L!=b.L)

		return a.L<b.L;

	return a.R<b.R;

}

int ans[maxn];

priority_queue <node > q;

int main()

{

	int ncase,n,i,j,cur,cnt;

	scanf("%d",&ncase);

	while(ncase--)

	{

		scanf("%d",&n);

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

			scanf("%d",&s[i].L);

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

		{

			scanf("%d",&s[i].R);

			s[i].id=i;

		}

		sort(s+1,s+1+n,cmp);

		cur=0;

		cnt=1;

		i=1;

		while(!q.empty())

			q.pop();

		while(1)

		{

			while(i<=n && s[i].L<=cur)

				q.push(s[i++]);

			if(q.empty())

				break;

			node temp=q.top();

			q.pop();

			if(temp.L<=cur && temp.R>=cur)

				cur++;

			ans[cnt++]=temp.id;

		}

		for(;i<=n;i++)

			ans[cnt++]=s[i].id;

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

		printf("%d",ans[1]);

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

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

		printf("\n");

	}

	return 0;

}