题解：P11820 [PA 2015] 健身房 / Siłownia

小清新贪心。

题意

现在有

n

个人和

k

个健身器材。

第

i

个人需要在

[l_i,r_i]

中的任意一个时刻去健身房

p_i

，一个健身房同一时刻只能有最多一个人。

一个方案的代价是，有多少时刻，满足这个时刻中健身房里有人。

构造一个代价最小的方案。

n\le 10^6

。

题解

首先来考虑，假如不存在两个人

i,j

，使得

r_i=r_j

且

p_i=p_j

，答案怎么算。

可以发现这是一个贪心，因为每一个人进入健身房的时间应当是越晚越好，这样能让更多的人一起被安排。

具体过程是这样的，我们从小到大枚举时间

t

。

首先若存在

l_i=t

，这说明我们可以安排

i

这个人了，将

i

这个人加到

p_i

这个 set 里面。

若存在一个人

i

，满足

r_i=t

，并且

i

这个人还没有安排健身房。

那么我们知道，

t

这个时刻就一定得有人在健身房了，我们考虑安排哪些人去健身房。

显然，对于同一类人（如果

p

相同我们就认为是一类人），应该选取一个

r_i

最小的人去健身房，直接 set 里面找就好了。

显然，关键的

t

只有

O(n)

个（即每一个人的左右端点），那么这是一个

O(n\log n)

的做法。

考虑为啥不能用这个做法做原题。

因为如果存在两个人

i,j

，有

r_i=r_j

，并且

p_i=p_j

。

那么我们在扫到

r_i-1

这个时刻的时候，就必须要安排一个人上去，否则

r_i

再安排的时候安排不下就爆炸了。

这个时候有一个方法是拿线段树或者什么东西维护一下，可能能做，但我们有更牛的做法。

假设此时存在这样的一对

i,j

，我们不妨假设

l_i\le l_j

。

那么我们直接令

r_i\gets r_i-1

就好了。

为什么呢，考虑我们的限制说明了有

[l_j,r_j]\subseteq [l_i,r_i]

，也就是说

j

能去健身房的时刻

i

也能去。

那么如果

i

在

r_i

这个时刻去了健身房，我们直接让

i,j

两个人去健身房的时刻交换一下，显然交换完的方案依然合法。

所以如果有解，我们就一定能够构造出，

i

不在

r_i

时刻去健身房的方案。

那么我们一直做这个操作，做到不存在这样的

i,j

为止。

假设此时存在一个

k

满足

l_k>r_k

，那么无解。

否则我们可以跑上面那个 set 维护的贪心。

那么如何快速做这个操作呢，把所有

p_i

相同的人放在一起，然后按照

l_i

从大到小进行排序，然后 set 维护连续段即可。

时间复杂度

O(n\log n)

，并且我们只使用了 set，这实在是太牛了！

题解

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
	int s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline ll lread()
{
	ll s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
struct node
{
	int l,r,p,id;
}a[1000005];
struct nod
{
	int id,op,t;
	nod(int id=0,int op=0,int t=0):id(id),op(op),t(t){}
};
set<pi>rest[1000005];
set<int>S;
int qans[1000005];
map<int,int>to;
vc<nod>event;
int n,k,c;
set<pi>wtf;
inline void cover(int tim)
{
	vc<int>P;
	for(int i:S)
	{
		qans[a[(*rest[i].begin()).second].id]=tim;
		rest[i].erase(rest[i].begin());
		if(!rest[i].size()) P.push_back(i);
	}
	for(int i:P) S.erase(i);
}
inline int get(int v)
{
	int ans;
	auto it=wtf.upper_bound(pi(v+1,-1));
	if(it==wtf.begin()||(--it)->second<v) ans=v,wtf.insert(pi(v,v));
	else
	{
		int L=it->first,R=it->second;wtf.erase(it);
		while(true)
		{
			it=wtf.upper_bound(pi(v,-1));
			if(it==wtf.begin()||(--it)->second<L-1){ ans=L=L-1;break;}
			L=it->first;wtf.erase(it);
		}
		wtf.insert(pi(L,R));
	}
	return ans;
}
int main()
{
	n=read(),k=read();
	for(int i=1;i<=n;i++) a[i].l=read(),a[i].r=read(),a[i].p=read(),a[i].id=i;
	sort(a+1,a+n+1,[](node a,node b)
	{
		if(a.p!=b.p) return a.p<b.p;
		return a.l>b.l;
	});

	for(int i=1;i<=n;i++)
	{
		if(!to.count(a[i].p)) to[a[i].p]=++c;
		a[i].p=to[a[i].p];
	}

	for(int l=1,r;l<=n;l=r)
	{
		r=l+1;
		while(r<=n&&a[r].p==a[l].p) r++;
		// printf("%d ~ %d\n",l,r-1);
		for(int j=l;j<r;j++)
		{
			a[j].r=get(a[j].r);
			if(a[j].l>a[j].r)
			{
				printf("NIE\n");
				return 0;
			}
			event.push_back(nod(j,0,a[j].l));
			event.push_back(nod(j,1,a[j].r));
		}
		wtf.clear();
	}

	sort(event.begin(),event.end(),[](nod a,nod b)
	{
		if(a.t!=b.t) return a.t<b.t;
		return a.op<b.op;
	});

	// for(int i=1;i<=n;i++) printf("%d %d %d\n",a[i].l,a[i].r,a[i].p);

	int ans=0;
	for(auto p:event)
	{
		if(p.op==0)
		{
			int q=p.id;
			rest[a[q].p].insert(pi(a[q].r,q));
			S.insert(a[q].p);
		}
		else
		{
			int q=p.id,P=a[q].p;
			if(rest[P].find(pi(a[q].r,q))!=rest[P].end()) ans++,cover(a[q].r);
		}
	}

	printf("%d\n",ans);
	for(int i=1;i<=n;i++) printf("%d\n",qans[i]);
	return 0;
}

题解：P11820 [PA 2015] 健身房 / Siłownia

文章操作

题意

题解

题解

相关推荐

评论

题解：P11820 [PA 2015] 健身房 / Siłownia