第十四届蓝桥杯省赛 Python B 组 D 题——管道(AC)

这篇具有很好参考价值的文章主要介绍了第十四届蓝桥杯省赛 Python B 组 D 题——管道(AC)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 管道

1. 问题描述

有一根长度为 len \text{len} len 的横向的管道,该管道按照单位长度分为 len \text{len} len 段,每一段的中央有一个可开关的阀门和一个检测水流的传感器。

一开始管道是空的,位于 L i L_i Li 的阀门会在 S i S_i Si 时刻打开,并不断让水流入管道。

对于位于 L i L_i Li 的阀门,它流入的水在 T i T_i Ti ( T i ≥ S i T_i \geq S_i TiSi) 时刻会使得从第 L i − ( T i − S i ) L_i - (T_i - S_i) Li(TiSi) 段到第 L i + ( T i − S i ) L_i + (T_i - S_i) Li+(TiSi) 段的传感器检测到水流。

求管道中每一段中间的传感器都检测到有水流的最早时间。

2. 输入格式

输入的第一行包含两个整数 n , len n,\text{len} n,len,用一个空格分隔,分别表示会打开的阀门数和管道长度。

接下来 n n n 行每行包含两个整数 L i , S i L_i,S_i Li,Si,用一个空格分隔,表示位于第 L i L_i Li 段管道中央的阀门会在 S i S_i Si 时刻打开。

3. 输出格式

输出一行包含一个整数表示答案。

4. 样例输入

3 10
1 1
6 5
10 2

5. 样例输出

5

6. 评测用例规模与约定

对于 30 30 30% 的评测用例, n ≤ 200 n \leq 200 n200 S i , len ≤ 3000 S_i, \text{len} \leq 3000 Si,len3000

对于 70 70 70% 的评测用例, n ≤ 5000 n \leq 5000 n5000 S i , len ≤ 1 0 5 S_i, \text{len} \leq 10^5 Si,len105

对于所有评测用例, 1 ≤ n ≤ 1 0 5 ​ 1 \leq n \leq 10^5​ 1n105 1 ≤ S i , len ≤ 1 0 9 ​ 1 \leq S_i,\text{len} \leq 10^9​ 1Si,len109 1 ≤ L i ≤ len​ 1 \leq L_i \leq \text{len}​ 1Lilen L i − 1 < L i ​ L_{i-1} < L_i​ Li1<Li

2. 解题思路

对于一个时间点 x x x,如果此时所有传感器都能检测到水流,那么当时间点大于 x x x 时也一定保证所有传感器都能检测到水流。题目要求我们找到满足条件的最小时间点,因为答案具有二段性,所以我们可以想到二分答案。

有了二分的思路后,问题转换为对于一个确定的时间点 x x x,我们如何判断此时所有传感器都能检测到水流?仔细思考,当时间确定后,对于一个位于 a i a_i ai 且开启时间为 S i ( S i ≤ x ) S_i(S_i \leq x) Si(Six) 的阀门,它的水流实际就是一条覆盖区间 [ a i − ( x − S i ) , a i + ( x − S i ) ] [a_i-(x-S_i),a_i+(x-S_i)] [ai(xSi),ai+(xSi)] 的线段。

我们可以将所有 S i ≤ x S_i \leq x Six 的阀门都进行转换,实际上得到的就是若干条线段。判断所有传感器是否都能检测到水流,等价于判断能否用这若干条线段覆盖区间 [ 1 , len ] [1,\text{len}] [1,len],问题接着转换为区间覆盖问题。

区间覆盖是一个经典问题。我们可以按区间的左端点来排序这些区间。接下来,我们检查这些区间是否覆盖了整个管道。如果第一个区间的左端点大于 1 1 1,那么表示管道的开始部分没有被覆盖,直接返回 false。否则我们设一个变量 r r r 表示可到达的最远距离, r r r 的初始值为第一个区间的右端点。我们接着检查其他区间是否与 r r r 相邻或重叠。如果当前区间和 r r r 相邻或重叠,我们将当前区间的右端点和 r r r 取最大值。最后如果 r ≥ len r \geq \text{len} rlen 则说明成功覆盖所有区间,否则说明没有。

回过头来考虑如何书写二分,设 l l l 为答案的下界, r r r 为答案的上界,如果二分得到的时间点 mid \text{mid} mid 符合条件,因为大于 mid \text{mid} mid 的时间点也一定符合条件,所以更新 r = mid r=\text{mid} r=mid,否则更新 l = mid+1 l=\text{mid+1} l=mid+1。我们重复这个过程,直到搜索范围的左右端点相等,此时就找到了最早的时间。 当然 l , r l,r l,r 的初始值我们也需要思考, l l l 显然为 1 1 1,而 r r r 我们需要考虑极限情况,即只存在一个最左或最右的阀门在最晚的时间点打开,显然此时需要的时间为 2 × 1 0 9 2 \times 10^9 2×109,所以 r r r 的初始值为 2 × 1 0 9 2 \times 10^9 2×109

时间复杂度: O ( n log ⁡ n 2 ) O(n\log n^2) O(nlogn2)文章来源地址https://www.toymoban.com/news/detail-728216.html

3. AC_Code

  • C++
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define sz(s) ((int)s.size())

int n, m;
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	vector<int> a(n), s(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> s[i];
	}
	auto check = [&](LL t) {
		std::vector<pair<LL, LL>> v;
		for (int i = 0; i < n; ++i) {
			if (t >= s[i]) v.push_back({a[i] - (t - s[i]), a[i] + (t - s[i])});
		}
		sort(v.begin(), v.end());
		if (sz(v) == 0 || v[0].first > 1) return false;
		LL r = v[0].second;
		for (int i = 1; i < sz(v); ++i) {
			if (v[i].first <= r + 1) r = max(r, v[i].second);
			else break;
		}
		return r >= m;
	};
	LL l = 1, r = 2e9;
	while (l < r) {
		LL mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << r << '\n';
	return 0;
}
  • Java
import java.util.*;

public class Main {
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int[] a = new int[n];
        int[] s = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = sc.nextInt();
            s[i] = sc.nextInt();
        }
        long l = 1, r = 2_000_000_000;
        while (l < r) {
            long mid = l + r >>> 1;
            if (check(mid, a, s)) r = mid;
            else l = mid + 1;
        }
        System.out.println(r);
    }

    private static boolean check(long t, int[] a, int[] s) {
        List<Pair<Long, Long>> v = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (t >= s[i]) {
                v.add(new Pair<>(a[i] - (t - s[i]), a[i] + (t - s[i])));
            }
        }
        v.sort(Comparator.comparingLong(Pair::getKey));
        if (v.size() == 0 || v.get(0).getKey() > 1) return false;
        long r = v.get(0).getValue();
        for (int i = 1; i < v.size(); ++i) {
            if (v.get(i).getKey() <= r + 1) r = Math.max(r, v.get(i).getValue());
            else break;
        }
        return r >= m;
    }

    static class Pair<K, V> {
        private final K key;
        private final V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}
  • Python
n, m = map(int, input().split())
a = []
s = []
for i in range(n):
    a_i, s_i = map(int, input().split())
    a.append(a_i)
    s.append(s_i)

def check(t):
    v = []
    for i in range(n):
        if t >= s[i]:
            v.append((a[i] - (t - s[i]), a[i] + (t - s[i])))
    v.sort()
    if len(v) == 0 or v[0][0] > 1:
        return False
    r = v[0][1]
    for i in range(1, len(v)):
        if v[i][0] <= r + 1:
            r = max(r, v[i][1])
        else:
            break
    return r >= m

l = 1
r = 2_000_000_000
while l < r:
    mid = (l + r) // 2
    if check(mid):
        r = mid
    else:
        l = mid + 1

print(r)

到了这里,关于第十四届蓝桥杯省赛 Python B 组 D 题——管道(AC)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第十四届蓝桥杯省赛c/c++大学B组题解

    个人答案,有错漏感谢指正哈 本题总分:5 分 【问题描述】   小蓝现在有一个长度为 100 的数组,数组中的每个元素的值都在 0 到 9 的范围之内。数组中的元素从左至右如下所示: 5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3

    2023年04月12日
    浏览(57)
  • 第十四届蓝桥杯省赛JavaB组试题E【蜗牛】个人题解Dijkstra堆优化

                                                                                     🍏🍐🍊🍑🍒🍓🫐🥑🍋🍉🥝                                               第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆

    2023年04月15日
    浏览(43)
  • 第十三届蓝桥杯省赛与国赛真题题解大汇总(十四届参赛者必备)

      大家好,我是执梗。本文汇总了我写的第十三届蓝桥杯所有省赛真题与国赛真题,会针对每道题打出我自己的难度评星⭐️,也会给出每道题的算法标签,帮助大家更有针对性的去学习和准备,当然许多题目由于难度或时间的原因暂未更新,如果有不懂的问题也可以在评

    2024年02月11日
    浏览(78)
  • 第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP?

                                                                                     🍏🍐🍊🍑🍒🍓🫐🥑🍋🍉🥝                                               第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆

    2024年02月01日
    浏览(51)
  • 十四届蓝桥杯省赛CB

    写的时候没跑出来,仅仅是因为给 (i*i) 加了括号,爆了int!!! 双精度浮点的表示范围:-1.79E+308 ~ +1.79E+308 基本类型:int 二进制位数:32(4字节) 最小值:Integer.MIN_VALUE= -2147483648 (-2的31次方) 最大值:Integer.MAX_VALUE= 2147483647 (2的31次方-1 double范围很大,基本不可能爆,不

    2024年02月08日
    浏览(46)
  • 第十四届蓝桥杯Python B组省赛复盘

    【问题描述】(5 分) 请求出在 12345678 至 98765432 中,有多少个数中完全不包含 2023 。 完全不包含 2023 是指无论将这个数的哪些数位移除都不能得到 2023 。 例如 20322175,33220022 都完全不包含 2023,而 20230415,20193213 则 含有 2023 (后者取第 1, 2, 6, 8 个数位) 。 【思路】 正则表达

    2024年02月02日
    浏览(53)
  • 2023年第十四届蓝桥杯省赛Java C组题解

    只做出来(ACDFGH),挑几个出来,答案不一定正确,但自己测试通过了 求1~20230408的和 这里就直接套等差数列的求和公式,答案:204634714038436   【问题描述】         有一个长度为n的数组(n是10的倍数),每个数 Ai 都是区间[0,9]中的整数,小明发现数组里每种数出现的次数不太

    2023年04月26日
    浏览(41)
  • 第十四届蓝桥杯大赛软件赛省赛(Python大学A组)

    2023年蓝桥杯    省赛真题 Python大学A组         试题A:特殊日期         试题B:分糖果         试题C:三国游戏         试题D:平均         试题E:翻转         试题F:子矩阵         试题G:阶乘的和         试题H:奇怪的数         试题

    2024年02月04日
    浏览(51)
  • 第十四届蓝桥杯大赛软件组省赛 Python大学A组 个人暴力题解

    4.23 update: 省一咯 Powered by: NEFU AB-IN 博主个人的暴力题解,基本很少是正解,求轻喷 题意 思路 模拟即可,本身想用Python自带的datetime库,结果发现年不能开那么大,就直接手写了 代码 题意 思路 DFS爆搜即可 代码 题意 思路 直接没思路,一看到数据范围瞬间怂了,脑子里想的

    2023年04月09日
    浏览(42)
  • 蓝桥杯嵌入式第十四届省赛题目解析

    前几天刚刚参加完第十四届的省赛,这届题目比我想象中的要难,其实想一想这也是应该的,以前的知识点都被摸透了,也是需要加入新的知识点了,但是我还是想说能不能别在我参加的时候加大题目难度啊。 不过听说隔壁单片机的省赛都比往年的国赛还难,这就有点离谱了

    2024年02月06日
    浏览(58)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包