首页 > 试题广场 >

新增的专线

[编程题]新增的专线

热度指数：655 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

Pony.ai 有N个office分布在不同地方(编号从0开始），某些office之间有部署专线，office之间可以通过专线间接连接（专线是双向的），例如guagnzhou和beijing之间有专线，guagnzhou和shenzhen之间有专线，那么beijing可以通过guangzhou与shenzhen间接地通讯，这条信路的总延时是两条专线的延时之和。两个office之间的通讯延时是他们之间延时最短的信路的延时。
Infra团队知道当前任意两个office之间的通讯延时。最近Infra团队希望在office a与 office b之间部署一条新的专线，希望这条专线的延时 t 尽可能大（出于成本考虑）同时延时最大的两个office之间的通讯延时与 t 之和小于k，你能帮忙求出这个 t 吗？

输入描述:

第一行一个正整数 N <= 1000，表示office的数目

接下来N行，每行N个非负整数，用空格分开。第i行第j个数表示当前office i和office j之间的通讯延时，保证小于1e9。

接下来一行3个整数，依次表示a，b，k。其中 。

输出描述:

输出一行一个整数，满足条件的t，注意t不能是负数。如果不存在满足条件的t，输出 -1。

示例1

输入

输出

说明

增加从office 1 到 office 2 之间延时 t = 0 的专线后，延时最大的两个office之间的延时为2。 而 t + 2 < 3 满足题意

算法知识视频讲解

Java

pein531

二分法

对于这种类似“最大值尽量小”或者“最小值尽量大”的问题一般都可以往二分上想，这里二分搜索的下界为0，上界为k。对于某个尝试的新专线延时t，我们枚举检查当加入这个专线后，会不会有哪两个office之间的延时加上t之后会不小于k。

（1）如果全部都是小于k的，说明此时的t是符合题意的，可以记录下它然后往右搜索，寻找更大的t；

（2）如果存在一个不小于k的情况，说明此时t太大了，需要往左搜索，寻找更小的t。

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] mat = new int[n][n];
        for(int i = 0; i < n; i++){
            String[] strs = br.readLine().split(" ");
            for(int j = 0; j < n; j++){
                mat[i][j] = Integer.parseInt(strs[j]);
            }
        }
        String[] params = br.readLine().split(" ");
        int a = Integer.parseInt(params[0]);
        int b = Integer.parseInt(params[1]);
        int k = Integer.parseInt(params[2]);
        int left = 0, right = k, ans = -1;
        while(left <= right){
            int t = left + ((right - left) >> 1);
            if(check(mat, a, b, t, k)) {
                ans = t;
                left = t + 1;
            }else{
                right = t - 1;
            }
        }
        System.out.println(ans);
    }

    private static boolean check(int[][] mat, int a, int b, int t, int k) {
        int n = mat.length;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                // 看是直接到快，还是走新的专线快
                int dij = Math.min(
                    mat[i][j], 
                    Math.min(
                        mat[i][a] + t + mat[b][j],
                        mat[i][b] + t + mat[a][j]
                    )
                );
                // 检查有没有哪两个office之间的通讯延时与t之和不小于k
                if(dij + t >= k){
                    return false;
                }
            }
        }
        return true;
    }
}

发表于 2022-04-21 21:21:11 回复(0)