侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【贪心】货仓选址

GabrielxD
2023-02-08 / 0 评论 / 0 点赞 / 81 阅读 / 757 字
温馨提示:
本文最后更新于 2023-02-08,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

104. 货仓选址 - AcWing题库


在一条数轴上有 NN 家商店,它们的坐标分别为 A1ANA_1 \sim A_N

现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。

为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数 NN

第二行 NN 个整数 A1ANA_1 \sim A_N

输出格式

输出一个整数,表示距离之和的最小值。

数据范围

1N1000001 \le N \le 100000 ,
0Ai400000 \le A_i \le 40000

输入样例:

4
6 2 9 1

输出样例:

12

解题

方法一:贪心算法

思路

设货仓的位置为 xx ,那么货仓到每家商店的距离之和为:sum=A1x+A2x+A3x++AN1x+ANxsum = |A_1 - x| + |A_2 - x| + |A_3 - x| + \dots + |A_{N-1} - x| + |A_N - x|
把首位两项结合,整理一下:sum=(A1x+ANx)+(A2x+AN1x)++(AN2x+AN2+1x)sum = (|A_1 - x| + |A_N - x|) + (|A_2 - x| + |A_{N-1} - x|) + \dots + (|A_{\lfloor\frac{N}{2}\rfloor} - x| + |A_{\lfloor\frac{N}{2}\rfloor + 1} - x|)
观察发现,如果此时货仓在每一项的商店中间时,距离之和取得最小值:sum=(ANA1)+(AN1A2)++(AN2+1AN2)sum = (A_N - A_1) + (A_{N - 1} - A_2) + \dots + (A_{\lfloor\frac{N}{2}\rfloor + 1} - A_{\lfloor\frac{N}{2}\rfloor})
此时货仓在中间的个商店之间(商店数量为偶数时)或在中间的商店上(商店数量为奇数时),也即中位数

所以要取得最小距离之和应该把所有商店排序后使用双指针指向两端,然后向内收缩并把指向的两项做差累和为距离。

代码

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

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            a[i] = (int) in.nval;
        }
        Arrays.sort(a);
        long ans = 0L;
        for (int l = 0, r = n - 1; l < r; ++l, --r) ans += a[r] - a[l];
        System.out.println(ans);
    }
}
0

评论区