CF822C [Hacker, pack your bags]!题解

Hacker, pack your bags!

https://ac.nowcoder.com/acm/problem/112136

前言

这是一道很棒的思维题/数据结构！

难度：2星
做法：二分，排序 $or$ 线段树

题意：

给定 $n,m$ 以及 $n$ 个区间，区间 $i$ 有左端点 $l_i$ 和右端点 $r_i$ 以及花费 $cost_i$ ,要求你选出两个区间,满足下面两个条件:

两个区间没有交集
两个区间的长度和等于 $m$ (这里的长度为 $r_i - l _i + 1$ )

现在要求你选出的这两个区间的权值和最小，输出最小权值和。

做法：

因为是两个区间，考虑枚举其中一个区间。

因为两个区间要不相交，所以很容易想到把所有区间按照其 $l$ 从小到大排序，如果 $l$ 相等，则按照 $r$ 从小到大排序。

通过枚举区间 $a$ ，只需要找到所有左端点 $l_b$ 大于其右端点 $r_a$ 的区间 $b$ ，这样子 $a$ , $b$ 两个区间就是不相交的。

可以通过二分找到第一个左端点 $l$ > $r_a$ 的区间,这样子所有左端点在这个找到的区间的左端点右边的区间都是满足条件的区间，假设找到的是第 $j$ 个区间，因为所有区间是按左端点 $l$ 排序好了的，所以从第 $j$ 到第 $n$ 个区间跟当前区间 $i$ 都是没有交点的。

找到 $[L_i,R_i]$ 内满足 $lenb = m - lena$ 的所有区间的权值最小值，也就是跟当前区间 $i$ 的长度之和为 $m$ 的所有区间中区间的权值最小的区间。
( $R_i$ 直接设置为 $n$ , $L_i$ 用之前提到的二分找到，如果不存在 $L_i$ ，那么说明这个区间是无法与其他区间满足条件的)

这样子就满足了第一个限制,并且每一张票都有了一个自己查询的区间： $[L_i,R_i]$ 。

对于枚举的每一个区间都进行查询很不方便，但是感觉可以用神奇数据结构来搞（目测线段树？

观察到每次要查的右区间是固定的，不妨将枚举到 $i$ 的时候需要查询的 $L_i$ 给记录下来，然后把 $L_i$ 按照从大到小排序。

这样子 O( $n$ ) 扫一遍过来，开个桶在扫的时候记录一下 $Min[len]$ ，也就是长度为 $len$ 的所有区间的权值最小值，这时候对于询问就直接O(1) 获得答案。

Code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 400005,INF = 100000000000000000;
int n , m ;
int Min[MAXN],cnt = 0;

struct Node {
    int l,r,cost;
} T[MAXN];

struct P {
    int L,D,F;
    //L记录查[L,R]的左端点L,D表示枚举到的区间的权值，F表示要找的长度 即长度为 m-lena 
} C[MAXN];

bool cmp(Node A , Node B)
{
    if(A.l != B.l)
    return A.l < B.l;
    return A.r < B.r;
}

int cmp1(P A, P B)
{
    return A.L > B.L;
}

inline int read()
{
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' && ch < '0' ; ch = getchar())if(ch == '-')flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar())x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

signed main()
{
    n = read() , m = read();
    for(int i = 1 ; i <= n ; i ++)
    T[i].l = read(),T[i].r = read(),T[i].cost = read();
    sort(T + 1 , T + 1 + n , cmp);//按照左端点从小到大排序，左端点相同的按照右端点从小到达排序
    for(int i = 1 ; i <= m ; i ++)Min[i] = INF;
    for(int i = 1 ; i <= n ; i ++)
    {
        int lena = T[i].r - T[i].l + 1;
        if(lena >= m){C[i].L = -1;continue;}
                //剪枝了一下，如果当前区间长度大于等于m了，另外一个区间需要长度小于等于0，不存在答案
        int K = n + 1;
        for(int j = log2(n - i + 1) ; j >= 0 ; j --)
            if(T[K - (1 << j)].l > T[i].r && K - (1 << j) >= 1)K -= (1 << j);//二分换成倍增了。
        if(K != n + 1)
            C[i].L = K , C[i].D = T[i].cost , C[i].F = m - lena;
        else C[i].L = -1;//题解里说的L不存在，赋值为-1
    }
    sort(C + 1 , C + 1 + n , cmp1);//按照L排序
    int now = 1,Ans = INF;
    for(int i = n ; i >= 1 ; i --)
    {
        if(C[now].L == -1)break;//如果没有询问了直接break
        int len = T[i].r - T[i].l + 1;
        Min[len] = min(Min[len],T[i].cost);//扫的时候记录长度为len的区间的权值最小值
        while(C[now].L == i && now <= n)一个点可能有多个询问，用while
        {
            if(C[now].L == -1)break;//没有询问了
            Ans = min(Ans,C[now].D + Min[C[now].F]);//O(1)获得答案，取min
            now ++;
        }
    }
    if(Ans == INF)    cout << -1;
    else cout << Ans;
    return 0;
}

下面是无注释版本的代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 400005,INF = 100000000000000000;
int n , m ;
int Min[MAXN],cnt = 0;

struct Node {
    int l,r,cost;
} T[MAXN];

struct P {
    int L,D,F;
} C[MAXN];

bool cmp(Node A , Node B)
{
    if(A.l != B.l)
    return A.l < B.l;
    return A.r < B.r;
}

int cmp1(P A, P B)
{
    return A.L > B.L;
}

inline int read()
{
    int x = 0 , flag = 1;
    char ch = getchar();
    for( ; ch > '9' && ch < '0' ; ch = getchar())if(ch == '-')flag = -1;
    for( ; ch >= '0' && ch <= '9' ; ch = getchar())x = (x << 3) + (x << 1) + ch - '0';
    return x * flag;
}

signed main()
{
    n = read() , m = read();
    for(int i = 1 ; i <= n ; i ++)
    T[i].l = read(),T[i].r = read(),T[i].cost = read();
    sort(T + 1 , T + 1 + n , cmp);
    for(int i = 1 ; i <= m ; i ++)Min[i] = INF;
    for(int i = 1 ; i <= n ; i ++)
    {
        int lena = T[i].r - T[i].l + 1;
        if(lena >= m){C[i].L = -1;continue;}
        int K = n + 1;
        for(int j = log2(n - i + 1) ; j >= 0 ; j --)
            if(T[K - (1 << j)].l > T[i].r && K - (1 << j) >= 1)K -= (1 << j);
        if(K != n + 1)
            C[i].L = K , C[i].D = T[i].cost , C[i].F = m - lena;
        else C[i].L = -1;
    }
    sort(C + 1 , C + 1 + n , cmp1);
    int now = 1,Ans = INF;
    for(int i = n ; i >= 1 ; i --)
    {
        if(C[now].L == -1)break;
        int len = T[i].r - T[i].l + 1;
        Min[len] = min(Min[len],T[i].cost);
        while(C[now].L == i && now <= n)
        {
            if(C[now].L == -1)break;
            Ans = min(Ans,C[now].D + Min[C[now].F]);
            now ++;
        }
    }
    if(Ans == INF)    cout << -1;
    else cout << Ans;
    return 0;
}

另外建议不要用 $cin$ ,如果用 $cin$ 评测得很慢，虽然不会超时，但是你得评测 $1$ 分半钟.....（因为一共136个点！）