「Codeforces 555B」Case of Fugitive

发表于 | | 阅读次数:
字数统计: 675 字

Description

题目链接：Codeforces 555B

有 $n$ 个狭窄的岛屿排成一排的群岛，我们将他们表示为直线上不相交的线段：岛屿 $i$ 的坐标为 $[l_i,r_i]$。保证对于所有的 $1\le i\le n-1$，都有 $r_i<l_{i+1}$。

你需要在所有相邻的岛屿之间架上桥梁。一座长度为 $a$ 的桥可以架在第 $i$ 和 $i+1$ 个岛屿之间，当且仅当存在 $l_i\le x\le r_i$，$l_{i+1}\le y\le r_{i+1}$ 满足 $y-x=a$。

现在你有 $m$ 座桥梁，第 $i$ 座桥梁的长度为 $a_i$，并且每座桥梁最多只能使用一次。请问是否可以把任意两个相邻的岛屿连通。如果可行，输出 Yes 和方案；否则输出 No。

数据范围：$2\le n\le 2\times 10^5$，$1\le m\le 2\times 10^5$，$1\le l_i\le r_i\le 10^{18}$，$1\le a_i\le 10^{18}$

Solution

我们先求出相邻两个岛屿之间能架的桥的长度区间，显然对于岛屿 $i,i+1$，长度区间为 $[l_{i+1}-r_i,r_{i+1}-l_i]$，记为 $[s_i,t_i]$。这就是说，我们要对每个 $i\in [1,n)$，配上一个 $a_j$ 满足 $s_i\le a_j\le t_i$。

考虑贪心策略：把所有的长度区间按照右端点为第一关键字，左端点为第二关键字，从小到大排序。对于第 $i$ 个区间，我们找到第一个不小于 $s_i$ 的 $a_j$ 与其配对。如果出现无解情况（找不到不小于 $s_i$ 的值，或者 $a_j>r_i$）就直接退出。这个过程可以通过 $\text{set}$ 实现。

时间复杂度：$O(n\log nm)$

Code

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
 
#include <cstdio>
#include <algorithm>
#include <set>

const int N=2e5+5;
int n,m,ans[N];
struct Inter {
    long long l,r;
    int id;
    bool operator < (const Inter &b)const {
        return r==b.r?l<b.l:r<b.r;
    }
} a[N];
struct Bridge {
    long long x;
    int id;
    bool operator < (const Bridge &b)const {
        return x<b.x;
    }
};

int main() {
    scanf("%d%d",&n,&m);
    long long lstL,lstR;
    scanf("%lld%lld",&lstL,&lstR);
    for(int i=1;i<n;++i) {
        long long L,R;
        scanf("%lld%lld",&L,&R);
        a[i].l=L-lstR,a[i].r=R-lstL,a[i].id=i;
        lstL=L,lstR=R;
    }
    std::multiset<Bridge> s;
    for(int i=1;i<=m;++i) {
        long long x;
        scanf("%lld",&x);
        s.insert(Bridge{x,i});
    }
    --n;
    std::sort(a+1,a+n+1);
    for(int i=1;i<=n;++i) {
        long long l=a[i].l,r=a[i].r;
        std::multiset<Bridge>::iterator it=s.lower_bound(Bridge{l,0});
        if(it==s.end()||it->x>r) return puts("No"),0;
        ans[a[i].id]=it->id,s.erase(it);
    }
    puts("Yes");
    for(int i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
    return 0;
}
0%