链接：https://ac.nowcoder.com/acm/problem/50937
来源：牛客网
题目描述
在一条数轴上有N家商店，它们的坐标分别为 A[1]~A[N]。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何
展开全文
题目链接 假设把货仓建在第k个商店的坐标上，那么左边有 k - 1 个商店，右边有 n - k - 1 个商店。 当k<n/2时，向右移一位，因为k-1<n-k-1，所以+(k-1)-(n-k-1)会使总距离减小，因此我们应当把k往右移，直到当 k-1 = n-k-1时，若再往右移，k-
展开全文
如果是个明眼人，可以看出来选中位数一定是最优解，此时答案一定是后一半的和减去前一半的和，即∑i=1n/2(vn−i+1−vi)\sum_{i=1}^{{n}/{2}}(v_{n-i+1}-v_i)∑i=1n/2(vn−i+1−vi)。
但是像我这样的大制杖就只能硬证。。。
我们求的是：
min
展开全文
这题一看就是排序，这里就说一下我的思路：首先将a数组排序，并令x为货仓的坐标，尽量使x左侧的商店与x右侧的商店之差尽量小，也就是说将x放在中位数的位置最好，中位数的坐标也就是a[(n+1)/2]，接着自然就附代码了。#include<bits/stdc++.h>using namespa
展开全文
直观的想，假设我们将货仓建在第k个商店的坐标上，那么货仓左边有 k - 1 个商店，右边有 n - k - 1 个商店，当我们将货仓向右移动一个单位，那么货仓距离左面所有的商店的距离就会增加一个单位，距离右面所有的商店的距离会减少一个单位，所以应当使左右商店的个数相同， k-1 = n-k-1, 那
展开全文
一种前缀和的解法
假如我们并不知道中位数就是最优解
先看暴力枚举的思路
1-index数组a存储货仓的坐标
先给a排个序
for i := 1 to n
a[i]距离左边货仓j: a[i] - a[j]
距离左边所有货仓就是 a[i] - (a[1] + a[2] +... + a[i - 1])
展开全文
注意点：
（1）最优位置是选在左中位数或右中位数处
（2）如果不在这两点，左右移动时增加的距离会大于减小的距离
N = int(input())
a = list(map(int, input().split()))
a.sort()
print(sum(abs(x - a[N // 2]) for
展开全文
思路
找中间点, 奇数则找这个点, 偶数则在中间随便取一个点就行, 或者端点也可以
把距离加起来就ok了
这个题也是acwing 基础课的模板题
ac 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 +
展开全文
题目描述：在一条数轴上有N家商店，它们的坐标分别为 A[1]A[N]。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。输入排序：第一行一个整数N，第二行N个整数A[1]A[N]。输出排序：一个整数，表示距
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
