[cf gym102059A]Dumae

一个很有趣的贪心题。题目链接

题目大意:有$n$个人在排队,每个人知道自己可能所在的区间,接下来有$m$对人数$(x,y)$,表示$x$在自己的位置能看到前面的$y$,问是否存在一种合理的排队方式使得输入的情况成立。

首先我们可以利用拓扑排序找出一部分人的排队顺序,同时还能判断是否有不成立的情况(存在环)。

接下来我们可以根据拓扑排序的顺序去缩减每个人对应的区间,假设$x$前面有$y$,$x\in[l_1,r_1],y\in[l_2,r_2]$,则这两个区间可以更新为:$x\in[l_1,min(r_1,r_2-1)],y\in[max(l_1+1,l_2),r2]$,这个更新代表$x$的右区间一定比$y$的右区间小,因为根据拓扑排序,$x$的位置不可能大于$y$的位置;同理,$y$的位置不可能小于$x$的位置,因此使用两遍循环去更新每个人的左右区间,然后开始贪心。

首先我们根据右区间从小到大排序。这样能够保证结果最优(证明略)。然后我们使用并查集去寻找每个人能够找到的最小位置,这样就能够将所有人分配完,如果分派不完,说明无解。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1000000+10;
const int INF=0x3f3f3f3f;

struct node{
int l,r,i,pos;
}a[maxn];
vector<int>vec[maxn],vec2[maxn];
int ru[maxn],nxt[maxn],res[maxn],cur[maxn];
int n,m,u,v;

bool cmp(node i,node j){
if(i.r==j.r) return i.l<j.l;
return i.r<j.r;
}
int find(int x){ return x==nxt[x]?x:nxt[x]=find(nxt[x]);}
bool bfs(){
int num=0;
queue<int>que;
for(int i=1;i<=n;i++){
if(ru[i]==0){
que.push(i);
cur[++num]=i;
}
}
while(!que.empty()){
int x=que.front();
que.pop();
for(int i=0;i<vec[x].size();i++){
int y=vec[x][i];
ru[y]--;
if(ru[y]==0){
que.push(y);
cur[++num]=y;
}
}
}
return num!=n;
}
void update(){//更新左右区间
for(int i=n;i>0;i--){
int x=cur[i];
for(int j=0;j<vec[x].size();j++){
int y=vec[x][j];
a[x].r=min(a[x].r,a[y].r-1);
}
}
for(int i=1;i<=n;i++){
int x=cur[i];
for(int j=0;j<vec2[x].size();j++){
int y=vec2[x][j];
a[x].l=max(a[x].l,a[y].l+1);
}
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d %d",&a[i].l,&a[i].r);
a[i].i=i;
}
while(m--){
scanf("%d %d",&u,&v);
vec[u].push_back(v);
vec2[v].push_back(u);
ru[v]++;
}
//判断是否有环
if(bfs()){
printf("-1\n");
return 0;
}
//计算每个重定义后的区间
update();
//按照右区间从小到大排序
sort(a+1,a+n+1,cmp);
//并查集计算每个元素应该所在的位置以及判断是否有不符合情况的问题存在
bool flag=0;
for(int i=1;i<=n+1;i++) nxt[i]=i;
for(int i=1;i<=n;i++){
if(a[i].l>a[i].r) flag=1;
else{
int x=find(a[i].l);
if(x==n+1 || x>a[i].r) flag=1;
else res[x]=a[i].i,nxt[x]=find(x+1);
}
}
if(flag) printf("-1\n");
else{
for(int i=1;i<=n;i++){
printf("%d\n",res[i]);
}
}
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------