【线段问题创新思路】Hacker, pack your bags! CodeForces - 822C

悠悠 2022-06-10 14:30 128阅读 0赞

Think:  
1知识点：线段问题  
2题意：n条线段，从其中选择2条线段长度(线段长度计算公式为r-l+1)之和为x的边权为最小的，若没有2条线段长度之和为x的，输出-1  
3思路：  
2 ≤ n, x ≤ 2e5，双重for循环暴力会超时，因此思考如何优化，借鉴前辈的思路，把所有的边正反记录两次，用sum\[t\]数组记录之前的可以作为前置匹配区间的区间长度为t的区间的最小权值  
4提示(注意type排序顺序)：  
特殊的需要注意的测试数据——需要加深思考

example input:
    2 4
    3 4 1
    4 5 1
    example output:
    -1

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    typedef long long LL;
    
    const int inf = 0x3f3f3f3f;
    const int N = 201400;
    
    struct Edge{
        int l, r, c;
        int type;
        bool operator < (const Edge &b) const{
            if(l == b.l)
                return type > b.type;/*注意当l相等时应该按照type降序排序*/
            return l < b.l;
        }
    }edge[N<<1];
    
    int cnt, sum[N];
    
    void add_edge(int l, int r, int c, int type);
    
    int main(){
        int n, x, i, l, r, c;
        LL ans;
        while(~scanf("%d %d", &n, &x)){
            cnt = 0;
            for(i = 0; i < n; i++){
                scanf("%d %d %d", &l, &r, &c);
                add_edge(l, r, c, 1);
                add_edge(r, l, c, -1);
            }
            sort(edge, edge+cnt);
    
            ans = inf*2;/*注意初始化的最大值应大于2e9*/
            memset(sum, 0, sizeof(sum));
            for(i = 0; i < cnt; i++){
                int t = abs(edge[i].r - edge[i].l) + 1;
                if(t >= x)
                    continue;
                if(edge[i].type == -1){
                    if(!sum[t] || sum[t] > edge[i].c){
                        sum[t] = edge[i].c;
                    }
                }
                else {
                    if(sum[x-t]){
                        if(ans > edge[i].c + sum[x-t])
                            ans = edge[i].c + sum[x-t];
                    }
                }
            }
            if(ans != inf*2)
                printf("%lld\n", ans);
            else
                printf("-1\n");
        }
        return 0;
    }
    void add_edge(int l, int r, int c, int type){
        edge[cnt].l = l;
        edge[cnt].r = r;
        edge[cnt].c = c;
        edge[cnt].type = type;
        cnt++;
    }