首页 > 试题广场 >

小强修水渠

[编程题]小强修水渠

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

在一张 $2D$ 地图上小强有 $n$ 座房子,因为地理位置的原因没有办法给每座房子提供水源,所以小强打算修建一条平行 $y$ 轴的水渠.因为这条水渠无限长.所以能够看做是一条平行于 $y$ 轴的直线. 现在小强想确定修建水渠的位置,能够使得这 $n$ 座房子到水渠的垂直距离和最小,请你输出最小的距离和.

输入描述:

第一行输入一个正整数.
接下来行,每行输入两个正整数,,分别表示每个房子所在的二维坐标.

输出描述:

输出一个整数表示答案

示例1

输入

输出

说明

当修建水渠位置的直线方程为或者时,都能获得最小距离和.

算法知识视频讲解

Isen-江江

大家千万注意，接受结果的参数类型需要为long型！

发表于 2021-08-12 10:34:19 回复(1)

pein531

水渠位置应该有个约束，必须穿过至少一座房子。由于水渠和y轴平行，所以本题中的y坐标就没有用了，是一个很简单的数学问题。

依题意，不妨设x{0..n-1}是个单调不减的数列，对于i∈[0,n)，目标是使∑|x_i-x|最小，要x到x₀和x_n-1的距离和最小，则x一定在x₀~x_n-1中，其到x₀和x_n-1的距离和均为x_n-1-x₀，排除掉边缘点x₀和x_n-1，x_1~x_n-2就满足条件，下面考虑该点还要到x₁和x_n-2的距离和最小，则x一定在x₁~x_n-2中……

每次排除掉边缘两个数据点可以得到x是数列x{0..n-1}的中位数，能够满足到任意一对边缘点的距离和都最小，即距离总和也达到了最小。事实上，使∑|x_i-x|最小也是中位数的基本性质。

scala版

import scala.io.StdIn

object Main {
    def main(args: Array[String]): Unit = {
        val n = StdIn.readInt
        var xArr = Array.ofDim[Int](n)
        for(i <- 0 until n){
            val pos = StdIn.readLine().split(" ")
            val x = pos(0).toInt
            xArr(i) = x
        }
        xArr = xArr.sorted
        val median = xArr(n / 2)
        var totalDistance = 0L
        for(i <- 0 until n) totalDistance += math.abs(xArr(i) - median)
        println(totalDistance)
    }
}

java版

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

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[] x = new int[n];
        for(int i = 0; i < n; i++)
            x[i] = Integer.parseInt(br.readLine().trim().split(" ")[0]);
        Arrays.sort(x);
        int median = x[n / 2];
        long res = 0;
        for(int i = 0; i < n; i++) res += Math.abs(median - x[i]);
        System.out.println(res);
    }
}

编辑于 2021-08-16 22:54:45 回复(0)

C/C++

成长的程序员

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//1.题目的答案其实和x轴的坐标无关系，只需要考虑y轴的数据；
//2.在输入数据的时候，是先输入的y，再输入x；
//3.假如只有两座房子，它们在y方向的距离为length，水渠只要在这两个端点之间(包括端点)，所得到的距离总和就是最短的，
//为length，如果水渠在两个端点之外，那就不行；

//4.对所有的纵坐标从小到大排序，把最外侧的两个点找出来，它俩到水渠的距离之和为(y[n-1] - y[0])，水渠在它俩之间；
//接着考虑第2个数和倒数第2个数，水渠应该调整到它俩之间去，这样它俩到水渠的距离之和为(y[n-2] - y[1])；
//水渠的位置调整后，并不违背之前所做的工作，因为水渠的位置还是在第1个值和最后那个值之间；
//同理考虑第3组，。。。。这一步完成后，水渠的位置在第3组数之间，同样在第2组数之间，因为第3组数在第2组数的内侧

//5.最后的结果要把所有的差值加起来，注意要声明为long long类型；
//6.每次操作的是两个数，如果数的总数是奇数个呢？最中间那个可以不考虑，因为可以把水渠选在这个值上
void solve(int n)
{
    vector<int> nums(n, 0);
    for (int i = 0; i < n; ++i)
    {
        int x = 0;
        cin >>  nums[i] >> x; //先输入y，再输入的x，真是干tn的
    }
    sort(nums.begin(), nums.end()); //排序
    int p1 = 0;
    int p2 = n - 1;
    long long ans = 0;
    while(p1 < p2) //从两端往中间收缩
    {
        ans += nums[p2] - nums[p1]; //保存一组结果
        ++p1;
        --p2;
    }
    cout << ans << endl;
}


int main()
{
    int n = 0;
    cin >> n;
    solve(n);
    return 0;
}

编辑于 2021-08-14 19:51:36 回复(0)

Ringo201909111548427

import math
n=int(input())
x=[]
for i in range(n):
    x.append(int(input().split()[0]))
x.sort()
x_river=x[int(n/2)]
ans=[abs(x_river-each_x)for each_x in x]
print(sum(ans))

发表于 2021-07-08 21:58:14 回复(0)

O_n2

优化目标：

$\min\sum|x_i-x|=\sum{((x_i-x)^{2})}^{1/2}$

每个绝对值函数都是凸函数，显然凸函数的和是凸函数，这是个凸优化问题。

令导数：

$\frac{df}{dx}=\sum\frac{x-x_i}{|x-x_i|}=\sum sign(x-x_i)=0$

显然在x左边的点和右边的点数量上要相等，最优的x必然在序列中间。

故中位数必然是一个最优点。

所以思路是：先排序，找到中间位置，左边的位置和与右边的位置和之差即为结果。

def compute(x, n):
    x.sort()
    m = n >> 1
    if n % 2:
        return sum(x[m+1:]) - sum(x[:m])
    else:
        return sum(x[m:]) - sum(x[:m])

发表于 2021-04-29 10:54:40 回复(0)

爆爆只是想帮忙

//注意int溢出就行

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin >> n){
        vector<vector<int>> pos(n, vector<int>(2));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 2; j++){
                cin >> pos[i][j];
            }
        }
        sort(pos.begin(), pos.end(), [&](auto& a, auto& b){
            return a[0] < b[0];
        });
        long sum = 0;
        int left = 0, right = n - 1;
        while(left < right){
            sum += pos[right][0] - pos[left][0];
            left++;
            right--;
        }
        cout << sum << endl;
    }
}

发表于 2022-03-13 11:08:46 回复(0)

StarJAY

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] positions = new long[n];
        for(int i = 0; i < n; i++){
            positions[i] = sc.nextLong();
            sc.nextLong();
        }
        // 从大到小排序
        Arrays.sort(positions);
        double res = 0;
        // 中位数作为水渠位置
        double mid = n % 2 == 1 ? positions[n / 2] : (positions[n / 2 - 1] + positions[n / 2]) / 2;
        // 求距离和
        for(Long x : positions){
            res += Math.abs(mid - x);
        }
        System.out.println((long)res);
    }
}

发表于 2021-06-09 09:53:51 回复(0)

中南大学李彬

#include<iostream>
#include<bits/stdc++.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;

ll Abs(ll a,ll b)
{
    if(a>b) return a-b;
    else return b-a;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    ll n;
    cin>>n;
    ll ans=0;
    ll X[n];
    ll Y[n];
    for(ll i=0;i<n;i++)
    {
        cin>>X[i]>>Y[i];
    }
    sort(X,X+n);
    ll mid=n/2;
    for(ll i=0;i<n;i++)
    {
        ans+=Abs(X[i],X[mid]);
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2021-06-02 09:41:07 回复(0)

500cc

#include <iostream>
#include <algorithm>
#include <vector>
#include <bits/stdc++.h>
#include <limits.h>
 
using namespace std;
 
 
int main(){
    int num;
    cin>>num;
    int temp;
    vector<int> arr;
     
    for(int i=0;i<num;i++){
        cin>>temp;
        arr.push_back(temp);
        cin>>temp;
    }
    sort(arr.begin(),arr.end());
     
    long long temp2=LLONG_MAX-1;
 
    for(int i=num/2;i<num/2+2;i++){
        long long result=0;
        for(int k=0;k<num;k++){
            result=abs(arr[k]-arr[i])+result;
        }
        if(result<temp2){
            temp2=result;
        }
    }
     
    cout<<temp2<<endl;
     
     
    return 0;
}

发表于 2021-05-26 00:30:34 回复(0)

有一个地方.

n = int(input())
tmp = []
ans = 0
for _ in range(n):
    x, y = map(int, input().split())
    tmp.append(x)
tmp.sort()
p1, p2 = 0, n - 1
while p1 < p2:
    ans += tmp[p2] - tmp[p1]
    p1 += 1
    p2 -= 1
print(ans)

发表于 2021-05-01 10:49:13 回复(0)

C/C++

糖心Timothy

直接贴代码如下：

include

using namespace std;

typedef long long ll;
ll n;

int main() {
cin >> n;
ll xi[n + 5];
ll yi[n + 5];
for (ll i = 0; i < n; i++) {
cin >> xi[i] >> yi[i];
}
sort(xi, xi + n);
ll mid = (n - 1) >> 1;
ll sum = 0;
for (ll i = 0; i < n; i++) {
sum += abs(xi[i] - xi[mid]);
}
cout << sum << endl;
return 0;
}

编辑于 2021-04-30 18:12:13 回复(0)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师阿里巴巴测试工程师 PHP工程师安全工程师游戏研发工程师 2021 数据库工程师信息技术岗区块链测试开发工程师大数据开发工程师数据分析师 Java工程师

上传者：小小

难度：

11条回答 41收藏 5092浏览

通过挑战的用户

想去东北泡澡的...

2022-12-26 21:39:05
牛客90130...

2022-12-04 12:49:11
菜丢

2022-11-11 21:00:35
YoungShawn

2022-11-06 15:21:17
clwycash

2022-10-30 21:48:14

小强修水渠

输入描述:

输出描述:

输入

输出

说明

直接贴代码如下：

include

include

问题信息

热门推荐

通过挑战的用户

相关试题