HDU5360 – Hiking(优先队列)

Hiking

【题意】一系列人，请设计一个邀请序列使得最多的人同意，一个人是否同意当且仅当他被邀请的时候有>=li && <= ri个人同意时，他才会同意，否则永远不会同意了，同意了也不会再改变。

【分析】把当前满足条件的人放进优先队列(按照r值小的优先)，假设当前有cnt个人同意，则把新满足li<=cnt(即li==cnt,每次只加一个人)的人都入队，然后把不满足条件ri<cnt的人都去掉，这样就能贪心的得出最多能邀请几个人。加个输入输出挂快的飞起。

【AC CODE】358ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXBUF = 10000,MAXOUT = 10000, MAXN = 100000+10;
char buf[MAXBUF], *ps = buf, *pe = buf+1;
inline void rnext(){
	if(++ps == pe)
		pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);
}
template <class T>
inline bool in(T &ans)
{
	ans = 0;
	T f = 1;
	if(ps == pe) return false;//EOF
	do{
		rnext();
		if('-' == *ps) f = -1;
	}while(!isdigit(*ps) && ps != pe);
	if(ps == pe) return false;//EOF
	do
	{
		ans = (ans<<1)+(ans<<3)+*ps-48;
		rnext();
	}while(isdigit(*ps) && ps != pe);
	ans *= f;
	return true;
}
char bufout[MAXOUT], outtmp[50],*pout = bufout, *pend = bufout+MAXOUT;
inline void write()
{
	fwrite(bufout,sizeof(char),pout-bufout,stdout);
	pout = bufout;
}
inline void out_char(char c){ *(pout++) = c;if(pout == pend) write();}
inline void out_str(char *s)
{
	while(*s)
	{
		*(pout++) = *(s++);
		if(pout == pend) write();
	}
}
template <class T>
inline void out_int(T x) {
	if(!x)
	{
		out_char('0');
		return;
	}
	if(x < 0) x = -x,out_char('-');
	int len = 0;
	while(x)
	{
		outtmp[len++] = x%10+48;
		x /= 10;
	}
	outtmp[len] = 0;
	for(int i = 0, j = len-1; i < j; i++,j--) swap(outtmp[i],outtmp[j]);
	out_str(outtmp);
}
struct NODE{
	int y,id;
	bool operator<(const NODE &t)const{
		return y > t.y;
	}
};
int ans[MAXN],x[MAXN],y[MAXN];
priority_queue<NODE> q;
vector<NODE> p[MAXN];

bool vis[MAXN];
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	in(t);
	while(t--)
	{
		int n;
		in(n);
		rep(i,0,n) in(x[i]);
		rep(i,0,n) in(y[i]);
		repe(i,0,n) p[i].clear();
		rep(i,0,n) p[x[i]].push_back(NODE{y[i],i+1});
		int cnt = 0;
		while(!q.empty()) q.pop();
		clc(vis,0);
		while(cnt < n)
		{
			rep(i,0,p[cnt].size()) q.push(p[cnt][i]);
			while(!q.empty() && q.top().y < cnt) q.pop();
			if(q.empty()) break;
			ans[cnt++] = q.top().id;q.pop();
			vis[ans[cnt-1]] = 1;
		}
		out_int(cnt),out_char('\n');
		repe(i,1,n) if(!vis[i]) ans[cnt++] = i;
		rep(i,0,cnt)
		{
			out_int(ans[i]);
			if(i < cnt-1)
				out_char(' ');
		}
		out_char('\n');
	}
	write();
	return 0;
}

作者： dawxy

https://github.com/dawxy 查看dawxy的所有文章