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(nlog n^2)

O(nlogn2)

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 = [&amp;](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;
}
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)

原文地址:https://blog.csdn.net/m0_57487901/article/details/132741203

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_4479.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注