首页 > 试题广场 >

新增的专线

[编程题]新增的专线
  • 热度指数: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

输入

3
0 2 3
2 0 5
3 5 0
1 2 3

输出

0

说明

增加从office 1 到 office 2 之间延时 t = 0 的专线后,延时最大的两个office之间的延时为2。 而 t + 2 < 3 满足题意
首先,假如一开始给的距离表确实已经是每两点的最短距离了。如果我们改变给定的a和b之间的距离(假设改到d),那么对于每对点i和点j,它们这时候的实际最短距离为min(table[i][j], table[i][a] + d + table[b][j], table[i][b] + d + table[a][j])。
于是可以用binary search来假设a和b的距离,按上述方法代入每对点i和点j,来看是否能符合要求。Time complexity: O(N^2 log k), Space complexity: O(N^2).
这方法试了结果通过。

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int n;cin>>n;
    vector<vector<int> > edges;
    for(int i=0;i<n;i++){
        vector<int> row;
        for(int j=0;j<n;j++){
            int cur;cin>>cur;row.push_back(cur);
        }
        edges.push_back(row);
    }
    int a,b,k;cin>>a>>b>>k;
    int lower = -1,upper = k;
    while(upper-lower>1){
        int mid = (upper+lower)/2,ok=1;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                int d = edges[i][j];
                d = min(d,edges[i][a] + edges[b][j] + mid);
                d = min(d,edges[i][b] + edges[a][j] + mid);
                if(d+mid>=k){
                    ok=0;
                    break;
                }
            }
            if(!ok)break;
        }
        if(!ok)upper = mid;
        else lower = mid;
    }
    cout<<lower<<endl;
    return 0;
}


编辑于 2020-07-14 03:56:26 回复(23)

二分法

对于这种类似“最大值尽量小”或者“最小值尽量大”的问题一般都可以往二分上想,这里二分搜索的下界为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)
import sys
n=map(int, sys.stdin.readline().split())[0]
matrix=[]
for _ in range(n):
    matrix.append(list(map(int, sys.stdin.readline().split())))
offa, offb, k=map(int, sys.stdin.readline().split())

left=-1
right=k
while right-left>1:
    mid=(right+left)//2
    flag=True
    for i in range(n):
        for j in range(n):
            d=min([matrix[i][j], 
                   matrix[i][offa]+mid+matrix[offb][j],
                   matrix[i][offb]+mid+matrix[offa][j]])
            if d+mid>=k:
                flag=False
                break
        if not flag:
            break
    if flag:
        left=mid
    else:
        right=mid
print(left)
还是超时。

二分查找,对于每个元素更新其最短路径值,然后判断该值是否已经不满足条件了,可以剪枝。
发表于 2021-04-04 20:57:10 回复(0)
N = int(input())
o = [[int(i) for i in input().split(" ")] for _ in range(N)] # office
a, b, k = [int(i) for i in input().split(" ")]
left = -1
right = k
while right-left > 1:
    mid = (left + right) // 2
    maxDelay = 0
    for i in range(N):
        for j in range(i,N):
            if i == a and j == b:
                maxDelay = max(maxDelay, mid)
            else:
                maxDelay = max(maxDelay, min(o[i][j],o[i][a]+mid+o[b][j],o[i][b]+mid+o[a][j]))
            if maxDelay + mid >= k: break
        if maxDelay + mid >= k: break
    if maxDelay + mid < k:
        left = mid
    else:
        right = mid
print(left)
20% case 超时
发表于 2020-12-09 20:05:14 回复(0)

热门推荐

通过挑战的用户