CF822C [Hacker, pack your bags]!题解

Hacker, pack your bags!

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

前言

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

难度:2星
做法:二分,排序 线段树

题意:

给定 以及 个区间,区间 有左端点 和 右端点 以及 花费 ,要求你选出两个区间,满足下面两个条件:

  • 两个区间没有交集
  • 两个区间的长度和等于 (这里的长度为 )

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

做法:

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

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

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

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

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

这样子就满足了第一个限制,并且每一张票都有了一个自己查询的区间:

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

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

这样子 O() 扫一遍过来,开个桶在扫的时候记录一下 ,也就是长度为 的所有区间的权值最小值,这时候对于询问就直接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;
}

另外建议不要用,如果用评测得很慢,虽然不会超时,但是你得评测分半钟.....(因为一共136个点!)

闲人碎语 文章被收录于专栏

刊载算法学习笔记以及一些题解

全部评论

相关推荐

牛客383479252号:9,2学生暑期实习失利开始投小厂,给这群人整自信了
点赞 评论 收藏
分享
咦哟,从去年八月份开始长跑,两处实习转正都失败了,风雨飘摇,终于拿到offer了更新一下面试记录:秋招:多部门反复面试然后挂掉然后复活,具体问了啥已经忘了,只是被反复煎炸,直至焦香😋春招:base北京抖音hr打来电话说再次复活,准备面试,gogogo北京抖音一面:六道笔试题:1.promise顺序2.定义域问题3.flat展开4.并发请求5.岛屿数量算法(力扣)深度,广度都写6.忘记了,好像也是算法,难度中等其他问题多是框架底层设计,实习项目重难点~~~秒过😇北京抖音二面:三道笔试题:(为什么只有三道是因为第三道没做出来,卡住了)1.中等难度算法(忘记啥题了,应该是个数组的)2.认识js的继承本质(手写继承模式,深入js的面相对象开发)3.手写vue的响应式(卡在了watch,导致挂掉)---后知后觉是我的注册副作用函数写得有问题,有点紧张了其他题目多是项目拷打,项目亮点,对实习项目的贡献~~~第二天,挂,but立马复活转战深圳客服当天约面深圳客服一面:六道笔试题,由于面过太多次字节,面试官叫我直接写,不用讲,快些写完😋,具体都是些继承,深拷贝(注意对数组对象分开处理,深层次对象,循环引用),加中等难度算法题~~~秒过深圳客服二面:口诉八股大战:大概囊括网络,浏览器渲染原理,动画优化,时间循环,任务队列等等(你能想到的简单八股通通拉出来鞭尸😋)算法题:笔试题6道:1:找出数组内重复的数,arr[0]-arr[n]内的数大小为[1-n],例如[1,2,2,3,3]返回[2,3],要求o(n),且不使用任何额外空间(做到了o(n),空间方面欠佳,给面试官说进入下一题,做不来了)2:原滋原味的继承(所以继承真滴很重要)3:力扣股票购买时机难度中等其他滴也忘记了,因为拿到offer后鼠鼠一下子就落地了,脑子自动过滤掉可能会攻击鼠鼠的记忆😷~~~秒过深圳客服三面:项目大战参与战斗的人员有:成员1:表单封装及其底层原理,使用成本的优化,声明式表单成员2:公司内部库生命周期管理成员3:第三方库和内部库冲突如何源码断点调试并打补丁解决成员4:埋点的艺术成员5:线上项目捷报频传如何查出内鬼成员6:大文件分片的风流趣事成员7:设计模式对对碰成员8:我构建hooks应对经理的新增的小需求的故事可能项目回答的比较流利,笔试题3道,都很简单,相信大家应该都可以手拿把掐😇~~~过过过无hr面后续煎熬等待几天直接hr打电话发offer了,希望大家也可以拿到自己心仪的offer
法力无边年:牛哇,你真是准备得充分,我对你没有嫉妒,都是实打实付出
查看19道真题和解析
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务