题解：P11820 [PA 2015] 健身房 / Siłownia
Wuyanru
·
·
题解
小清新贪心。
题目链接。
题意
现在有 n 个人和 k 个健身器材。
第 i 个人需要在 [l_i,r_i] 中的任意一个时刻去健身房 p_i，一个健身房同一时刻只能有最多一个人。
一个方案的代价是，有多少时刻，满足这个时刻中健身房里有人。
构造一个代价最小的方案。
## 题解
首先来考虑，假如不存在两个人 $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，这实在是太牛了！
## 题解
```c++
#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;
}
```