专栏首页ACM小冰成长之路51Nod-1671-货物运输

51Nod-1671-货物运输

ACM模版

描述

题解

官方题解:

首先我们需要注意到最重要的一点,所有运输方案同时进行,我们只需要计算最后到达的方案的花费时间的最小值。所以我们需要考虑的是一个极限情况,在这个极限情况下,其他运输方案全部是在允许范围内的。所以我们可以二分枚举这个极限情况,判断所有方案是否都在这个极限内,在的话就继续缩小极限,不在的话就放大极限。至于这个极限呢,涉及到传送门的位置,我们可以将传送门的位置标记为两个区间,初始化这两个区间无限大,然后通过遍历方案来不断压缩这个区间,如果所有的方案都通过后,区间依然是合法的,那么这种极限就是合法的,反之,同理。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 5e5 + 10;
const int INF = 0x3f3f3f3f;

int n, m;
int l[MAXN], r[MAXN];

bool check(int m)
{
    int st_l = -INF, st_r = INF, ed_l = -INF, ed_r = INF;
    for (int i = 1; i <= n; i++)
    {
        if (r[i] - l[i] <= m)
        {
            continue;
        }

        st_l = max(st_l, l[i] + r[i] - m);
        st_r = min(st_r, l[i] + r[i] + m);
        ed_l = max(ed_l, l[i] - r[i] - m);
        ed_r = min(ed_r, l[i] - r[i] + m);
        if (st_l > st_r)
        {
            return 0;
        }
        if (ed_l > ed_r)
        {
            return 0;
        }
    }

    return 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", l + i, r + i);
    }
    for (int i = 1; i <= m; i++)
    {
        if (l[i] > r[i])
        {
            swap(l[i], r[i]);
        }
    }

    int l = 0, r = n, m, ans = -1;
    while (l <= r)
    {
        m = (l + r) >> 1;
        if (check(m))
        {
            ans = m;
            r = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }

    printf("%d\n", ans);

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codevs3278[NOIP2013]货车运输

    3287 货车运输 2013年NOIP全国联赛提高组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题目描述...

    HansBug
  • P1967 货车运输

    题目描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想...

    attack
  • 51nod 1596 搬货物(Codeforces 587A Duff and Weight Lifting)(思维)

    题目链接(Codeforces):http://codeforces.com/contest/587/problem/A

    Ch_Zaqdt
  • P1772 [ZJOI2006]物流运输

    题目描述 物流公司要把一批货物从码头A运到码头B。由于货物量比较大,需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线,...

    attack
  • 货物快捷运输,高效协同办公是第一步

    广东华裕国际货运具有多年国际集装箱运输理货经验,本着“客户至上,信誉为本,优质服务”的宗旨,形成了集国际海空运,陆地拖车,报关报检,仓储配送,货运保险,外汇结算...

    腾讯企点
  • P1967 货车运输 未完成

    1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<c...

    attack
  • 故障分析 | 全局读锁一直没有释放,发生了什么?

    爱可生交付服务部团队北京 DBA,主要负责处理 MySQL 的 troubleshooting 和我司自研数据库自动化管理平台 DMP 的日常运维问题,对数据库...

    爱可生开源社区
  • 物联网如何改善交通运输?

    How-Is-IoT-Improving-Transportation_-1068x656-1.jpg

    用户4122690
  • AkShare-中国宏观-全社会客货运输量

    指以价值量形式表现的邮电通信企业为社会提供各类邮电通信服务的总数量。邮电业务量按专业分类包括函件、包 件、汇票、报刊发行、邮政快件、特快专递、邮政储蓄、集邮、公...

    数据科学实战

扫码关注云+社区

领取腾讯云代金券