首页 > 试题广场 >

数轴

[编程题]数轴
  • 热度指数：2207 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
牛牛非常喜欢和朋友们一起玩。
牛牛有n个朋友当前在一根数轴上,每个朋友当前在整数x[i]坐标位置。
牛牛向他们发出一个移动的信号,每个朋友就向左或者向右移动s距离(每个朋友的选择是独立的,都可以选择向左或者向右)。
为了在一起玩耍方便,牛牛希望移动之后最左边的朋友和最右边的朋友距离最近,牛牛想知道最近距离为多少。

例如牛牛有三个朋友分别所在数轴坐标为-7, 4, 7, s = 5
那么第一个朋友-7向右移动s,变为-2
第二个朋友4向左移动s,变为-1
第三个朋友7向左移动s,变为2。
现在最左和最右的朋友距离是4,没有比这个更优的方案了。

输入描述:
输入包括两行,第一行两个正整数n和s(2 ≤ n ≤ 50, 0 ≤ s ≤ 10^8),表示朋友的个数和移动的距离。
第二行包括n个正整数x[i](-10^8 ≤ x[i] ≤ 10^8),表示初始时每个朋友所在的坐标位置。


输出描述:
输出一个正整数,表示移动之后最左边的朋友和最右边的朋友最小距离为多少。
示例1

输入

3 5
4 -7 7

输出

4
算法知识视频讲解
添加回答
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, s;
    scanf("%d%d", &n, &s);
    int a[n];
    for(int i=0;i<n;i++)
        scanf("%d", &a[i]);
    sort(a, a+n);
    int d = a[n-1] - a[0];
    for(int i=0;i<n-1;i++){
        int l = min(a[0]+s, a[i+1]-s);
        int r = max(a[n-1]-s, a[i]+s);
        d = min(d, r-l);
    }
    printf("%d\n", d);
    return 0;
}

发表于 2020-10-02 01:03:02 回复(0)
更多回答
wylu头像 wylu 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]), s = Integer.parseInt(strs[1]);
        int[] x = new int[n];
        strs = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            x[i] = Integer.parseInt(strs[i]);
        }

        Arrays.sort(x);
        int dist = x[n - 1] - x[0];
        for (int left, right, i = 0; i < n - 1; i++) {
            right = Math.max(x[i] + s, x[n - 1] - s);
            left = Math.min(x[i + 1] - s, x[0] + s);
            dist = Math.min(dist, right - left);
        }
        System.out.println(dist);
    }
}

发表于 2019-03-13 00:19:14 回复(1)
XH！头像 XH！

问题转换：如果先把所有点先向左移动s，所有点的可选操作就变成了原地不动或向右移动2s。
其中，向左移动s的步骤可省略，不影响结果。

解析思路：

先考虑最左边的点，如果向右移动2s后仍在最右点的左边，那么定左边界为移动后的位置，否则定左边界为最右点。(此左边界表示不可再右移的边界)
右边界为一个动态的值，初始为最右点。
再从左向右考虑点，如果向右移动2s后在右边界左边，直接跳过。（因为这个点不可能成为边界点）
直到某个点向右移动在右边界的右边，有两种选择。

  1. 保持不动，则得到一个距离，右边界到当前点，更新最短距离
  2. 右移2s，则更新右边界
    之后的所有点都面临上面这两种情况，直到当前点位于了左边界右边。（因为左边界不可能在右移了，余下的点右移又会更新右边界，所有不用考虑了） 
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    private static int n;
    private static int s;
    private static int[] P;

    public static void main(String[] args){

        int loop = 1;

        Scanner scanner = new Scanner(System.in);

        //loop = scanner.nextInt();
        while (loop-- > 0) {

            n = scanner.nextInt();
            s = scanner.nextInt();
            P = new int[n];

            for (int i = 0; i < n; i++) {
                P[i] = scanner.nextInt();
            }

            solve();
        }

        scanner.close();
    }

    private static void solve() {
        Arrays.sort(P);

        int dist = P[n - 1] - P[0];
        int move = s + s;
        int i = 0;
        int right = P[n - 1];
        int left = P[i] + move < right ? P[i++] + move : right; // 定左边界

        while (P[i] + move <= right) ++i; // 跳过移动后在右边界左边的点
        while (i < n && P[i] < left) { // 当前在左边界左边，移动后在右边界右边
            if(right - P[i] < dist) dist = right - P[i];
            right = P[i++] + move;
        }
        if(right - left < dist) dist = right - left;

        System.out.println(dist);
    }
}
发表于 2018-07-24 22:55:57 回复(1)
ynlybjl头像 ynlybjl
代码参考自wylu，采用遍历中心点的思路，解释一下以x[i]为中心点时（即从x[0]到x[i]右移，从x[i+1]到x[n-1]左移），左右边界是怎么确定的：

编辑于 2019-04-25 18:32:27 回复(0)
绅士喵头像 绅士喵
        想象一下我们上体育课的时候，如果我们站成一队，老师喊以某位同学为中心集合，左边的同学就会右移，右边的同学左移，大家肯定不会随意移动。
        类比到这道题中，稍微不同的是所有的点都要移动。那么我们就找一个中心点c，c（包括c）左边的点向右移动，c右边的点向左移动，移动完成后找到最左边的点和最后边的点，求出距离，然后判断距离的最小值即可。
        假设有n个点，我们不知道哪个点作为中心点的时候有最优解，所以从最左边开始，试n - 1次即可。最右边的点不可能是中心点，如果是的话，所有的点都向左移动，这和初始状态没有区别的。

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
 
using namespace std;
 
int main(int argc, char *argv[])
{
    int i, j, n, s, distance, left, right;
    vector<int> arry;
     
    cin >> n >> s;
    for(i = 0; i < n; i++)
    {
        cin >> j;
        arry.push_back(j);
    }
    sort(arry.begin(), arry.end()); //所有的点从左到右排序
    
    distance = arry[n - 1] - arry[0];
    for(i = 0; i < n - 1; i++) //i是分割点，i左边的点右移（包括i），i右边的点左移
    {
        left = INT_MAX; //记录最左边的点
        right = INT_MIN; //记录最右边的点
        for(j = 0; j <= i; j++) 
        {
            left = (left < arry[j] + s) ? left : (arry[j] + s);
            right = (right > arry[j] + s) ? right : (arry[j] + s);
        }
        for(; j < n; j++)
        {
            left = (left < arry[j] - s) ? left : (arry[j] - s);
            right = (right > arry[j] - s) ? right : (arry[j] - s);
        }
        distance = (distance < right - left) ? distance : (right - left);
    }
    cout << distance << endl;
     
    return 0;
}

发表于 2019-01-29 22:06:02 回复(0)
羚羊在找内推头像 羚羊在找内推 
为什么我觉得最短距离不应该大于S呢, 假如最左点和最右点之间距离大于S,只需要两回合
最左点向右移动2S,其他的点先左后右回到原位置上.这样距离就小于S了.
不太明白这个答案是为什么
42 824
527 -168 795 113 319 24 613 661 -829 763 737 541 -717 981 -12 512 
898 -87 73 -968 -553 880 228 -586 -265 -211 -3 -252 -941 491 -967 
-766 -616 253 -629 293 428 744 -778 -203 -321 222

1416  为什么最短距离大于S

发表于 2019-07-06 22:22:09 回复(9)
Hewitt头像 Hewitt
可以明确我们肯定是要将左边的连续的一段向右移，右边的连续的一段向左移，来达到最终距离最小。（可以证明先向左再先右又向左这种交叉移动方法一定不是最优解），那么我们可以枚举端点i，1~i全部向右移，i+1~n全部向左移，维护答案的最小值即可。 
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9+7;
int pos[55];
int main(){
    int n,s;
    scanf("%d %d",&n,&s);
    for(int i=1;i<=n;i++)scanf("%d",&pos[i]);
    sort(pos+1,pos+1+n);
    int ans = INF,maxx,minn;
    for(int i=1;i<n;i++){  ///枚举端点 1~i向右  i+1~n向左
        maxx = -INF,minn = INF;
        for(int j=1;j<=i;j++){
            maxx = max(maxx,pos[j]+s);
            minn = min(minn,pos[j]+s);
        }
        for(int j=i+1;j<=n;j++){
            maxx = max(maxx,pos[j]-s);
            minn = min(minn,pos[j]-s);
        }
        ans = min(ans,maxx-minn);
    }
    printf("%d\n",ans);
}

发表于 2019-06-26 11:19:11 回复(0)
Python
雾非雾selina头像 雾非雾selina 
n,s=list(map(int,input().split()))
x=list(map(int,input().split()))
x.sort()
res=float('inf')
for i in range(n-1):
    left=min(x[0]+s,x[i+1]-s)
    right=max(x[i]+s,x[-1]-s)
    res=min(right-left,res)
print(res)
#找到切分点，切分点及其以前的点向右移动，切分点后面的点向左移动
发表于 2019-06-05 20:41:30 回复(0)
C/C++
牛客549207409号头像 牛客549207409号
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
int main()
{
    int n;
    long long s,a;
    while(std::cin>>n>>s)
    {
        std::vector<long long>x;
        for(int i=0;i<n;i++)
        {
            std::cin>>a;
            x.push_back(a);
        }
        sort(x.begin(),x.end());
        long long left1,left2,right1,right2;
        long long min=1000000000;
        for(int i=0;i<n-1;i++)
        {
            left1=x[0]+s;
            right1=x[i]+s;
            left2=x[i+1]-s;
            right2=x[n-1]-s;
            long long d=abs(std::max(right1,right2)-std::min(left1,left2));
            if(d<min)min=d;
        }
        std::cout<<min<<std::endl;
    }
    return 0;
}
发表于 2020-09-20 14:26:51 回复(0)
ukaii头像 ukaii 
import sys
n, s = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
res = arr[-1] - arr[0]
for i in range(n - 1):
    cur = [arr[0] + 2*s, arr[i] + 2*s, arr[i + 1], arr[-1]]
    res = min(res, max(cur) - min(cur))
print(res)

编辑于 2020-08-06 23:45:56 回复(0)
浪少头像 浪少 
/*
参考自：wylu
思路：中心遍历，以-2 1 2 3 4 5 6（排序后），距离 s=5 为例
假设此时以 1 为中心，设其下标为 i，1 左边的往右移动，右边的往左边移动，距离为s
此时的右边界 right=Max(1+s，6-s)，即right=Max(a[i]+s,a[n-1]-s)
     左边界 left=Min(2-s,-2+s),即 left=Min(a[i+1]-s,a[0]+s)
依次从 0 开始遍历，找出最佳中心点
*/
import java.util.*;
public class Main {
    public static void main(String args[]){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int s=scanner.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++){
            a[i]=scanner.nextInt();
        }
        Arrays.sort(a);
        int dist=a[n-1]-a[0];
        int right,left;
        for(int i=0;i<n-1;i++){
            right=Math.max(a[i]+s,a[n-1]-s);
            left=Math.min(a[i+1]-s,a[0]+s);
            dist=Math.min(dist,right-left);
        }
        System.out.println(dist);
    }
}

发表于 2019-11-09 21:01:42 回复(0)
hpj03头像 hpj03
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,s;
    scanf("%d %d",&n,&s);
    vector<int>rec(n,0);
    for(int i=0;i<n;i++)
        scanf("%d",&rec[i]);
    sort(rec.begin(),rec.end());
    int ans = rec[n-1]-rec[0];
    for(int i=0;i<n-1;i++){
        int left = min(rec[i+1]-s,rec[0]+s);
        int right = max(rec[i]+s,rec[n-1]-s);
        ans = min(ans,right-left);
    }
    printf("%d",ans);
    return 0;
}
//   中心点左侧的点一定右移，右侧的点一定左移。假设t为右移的点，t左侧点如果右移会增大下界（最左点坐标）同时不超过上界（移动后还在t的左边），所以t的左侧应该全是右移，同理左移。最终形如->->-<-<-<，所以遍历中心点即可
发表于 2019-04-08 11:18:59 回复(0)
不知道做算法还是做py的喜茶头像 不知道做算法还是做py的喜茶
可不可以判断这个数的坐标，如果大于0，那么减s，如果小于0，那么加s，然后再进行排序，求距离
发表于 2018-08-11 01:57:36 回复(3)
提交观点

问题信息

C++工程师 贪心 模拟 网易 2018
上传者：小小
难度：
13条回答 5187浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号