Wuyanru's blog
0%

[PA2015] Siłownia

发表于 分类于 ，

小清新贪心。

题目链接。

题意

现在有 个人和 个健身器材。

第 个人需要在 中的任意一个时刻去健身房 ，一个健身房同一时刻只能有最多一个人。

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

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

。

题解

首先来考虑，假如不存在两个人 ，使得 且 ，答案怎么算。

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

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

首先若存在 ，这说明我们可以安排 这个人了，将 这个人加到 这个 set 里面。

若存在一个人 ，满足 ，并且 这个人还没有安排健身房。

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

显然，对于同一类人（如果 相同我们就认为是一类人），应该选取一个 最小的人去健身房，直接 set 里面找就好了。

显然，关键的 只有 个（即每一个人的左右端点），那么这是一个 的做法。

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

因为如果存在两个人 ，有 ，并且 。

那么我们在扫到 这个时刻的时候，就必须要安排一个人上去，否则 再安排的时候安排不下就爆炸了。

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

假设此时存在这样的一对 ，我们不妨假设 。

那么我们直接令 就好了。

为什么呢，考虑我们的限制说明了有 ，也就是说 能去健身房的时刻 也能去。

那么如果 在 这个时刻去了健身房，我们直接让 两个人去健身房的时刻交换一下，显然交换完的方案依然合法。

所以如果有解，我们就一定能够构造出， 不在 时刻去健身房的方案。

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

假设此时存在一个 满足 ，那么无解。

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

那么如何快速做这个操作呢，把所有 相同的人放在一起，然后按照 从大到小进行排序，然后 set 维护连续段即可。

时间复杂度 ，并且我们只使用了 set，这实在是太牛了！

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#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;
}