贪心：绝对值不等式
104. 货仓选址
在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1$ ~ $A_N$ 。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
输入格式
第一行输入整数 $N$ 。
第二行 N 个整数 $A_1$ ~ $A_N$ 。
输出格式
输出一个整数，表示距离之和的最小值。
数据范围： $1 ≤ N ≤ 100000$
输入样例：
4
6 2 9 1
输出样例：
12
解法一
货仓位置为 $A_i$ ，修建点为 $x$ ，那么货仓到 $x$ 点的距离之和为： $$ \begin{aligned} f(x) &= \sum_{i=0}^{n-1}|A_i-x| \\ &= |A_0-x|+|A_1-x|+…+|A_{n-2}-x|+|A_{n-1}-x| \\ &= (|A_0-x|+|A_{n-1}-x|) + (|A_1-x|+|A_{n-2}-x|) + … + (|A_{mid-1}-x|+|A_{mid+1}-x|) \\ &\geq(A_{n-1}-A_0) + (A_{n-2}-A_1) +…+ (A_{mid+1}-A_{mid-1}) \end{aligned} $$
当且仅当 $x$ 取在 $A_n$ 和 $A_1$ 中间， $A_{n-2}$ 和 $A_2$ 中间。.. 以及 $A_{mid+1}$ 和 $A_{mid-1}$ 中间时，不等式取得最小值，即 $X$ 为 $A_i$ 中位数时（奇偶同理）
代码实现如下：
import java.util.*;
import java.io.*;
class Main {
public static void main(String... args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int N = Integer.parseInt(br.readLine());
int[] A = read(br);
Arrays.sort(A);
int mid = A[(N-1)/2]; // 下取整
int res = 0;
for (int i = 0; i < N; i++) {
res += Math.abs(A[i]-mid);
}
System.out.println(res);
}
public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}
462. 最少移动次数使数组元素相等 II
Difficulty: 中等
给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加 1 或减 1。 您可以假设数组的长度最多为 10000。
例如：
输入：
[1,2,3]
输出：
2
说明：
只有两个动作是必要的（记得每一步仅可使其中一个元素加 1 或减 1）：
[1,2,3] => [2,2,3] => [2,2,2]
解法一
同上，不多解释
class Solution {
public int minMoves2(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int res = 0;
for (int i = 0; i < n; i++) {
res += Math.abs(nums[i]-nums[n>>1]);
}
return res;
}
}
912. 最佳见面地点
有一群住在不同地方的朋友（两个或以上）想要在某地见面，要求他们去往目的地的路程和最短。现在给一个 0、1 组成的二维数组，1 表示此地有一个人居住。使用曼哈顿距离作为计算总距离，公式为： $(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|$
样例 1:
输入：
[[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]]
输出：
6
解释：
点 (0, 2) 是最佳见面地点，最小的路程总和为 2+2+2=6，返回 6。
样例 2:
输入：
[[1,1,0,0,1],[1,0,1,0,0],[0,0,1,0,1]]
输出：
14
解法一
和前面一样 $$ f(n) = \sum_{i=0}^{n-1}(|x_i-x| + |y_i-y|) = \sum_{i=0}^{n-1}|x_i-x| + \sum_{i=0}^{n-1}|y_i-y| $$ 所以我们分别取 $x_i$ 和 $y_i$ 中点就行了
import java.util.*;
import java.io.*;
class Solution {
/**
* @param grid: a 2D grid
* @return: the minimize travel distance
*/
public int minTotalDistance(int[][] grid) {
// Write your code here
int n = grid.length;
int m = grid[0].length;
List<Integer> xlis = new ArrayList<>();
List<Integer> ylis = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) {
xlis.add(i);
ylis.add(j);
}
}
}
Collections.sort(xlis);
Collections.sort(ylis);
int xmid = xlis.get(xlis.size()>>1);
int ymid = ylis.get(ylis.size()>>1);
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 1) {
res += Math.abs(i-xmid) + Math.abs(j-ymid);
}
}
}
return res;
}
}
1703. 得到连续 K 个 1 的最少相邻交换次数
Difficulty: 困难
给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动，你可以选择 相邻 两个数字并将它们交换。
请你返回使 nums 中包含 k 个连续 1 的最少交换次数。
示例 1：
输入：nums = [1,0,0,1,0,1], k = 2
输出：1
解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。
示例 2：
输入：nums = [1,0,0,0,0,0,1,1], k = 3
输出：5
解释：通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。
示例 3：
输入：nums = [1,1,0,1], k = 2
输出：0
解释：nums 已经有连续 2 个 1 了。
提示：
- 1 <= nums.length <= 105
nums[i]要么是0，要么是1。- 1 <= k <= sum(nums)
解法一
42th 双周赛 T4，相比上面的题就有了一些思维的转换。
我们要把 $k$ 个 1 聚拢在一起，我们设定原始位置为 $A_0$ ~ $A_k-1$ ，聚集后的位置为 $X, X+1, X+2…., X+k-1$ 。推导过程如下：
交换次数为：
$$ f(k) = \sum_{i=0}^{k-1}|A_i-(X+i)| $$
要求这个式子的最小值，将式子转换一下，设 $A_i=B_i+i$ ，那么我们的式子就变成了
$$ f(k) = \sum_{i=0}^{k-1}|B_i-X| $$
根据我们 [上面的结论](#104-货仓选址），这个式子当 $X$ 取在 $B_i$ 中位数的时候，取得最小值。此时 $X=B_{mid}$ （奇偶同理)
$$ \begin{aligned} f(k) &= \sum_{i=l}^r|B_i-B_{mid}| \\ &= \sum_{i=l}^{mid}(B_{mid}-B_i) + \sum_{i = mid+1}^{r}(B_i-B_{mid}) \\ &= B_{mid} (2mid-l-r+1) - \sum_{i = l}^{mid}B_i + \sum_{i = mid+1}^{r}B_i \end{aligned} $$
前半部分可以直接计算得到，后半部分可以通过预处理前缀和快速求得，如此我们就可以在 $O(1)$ 的时间内滑窗求出窗口内 1 需要交换的次数，滑动过程中统计出最小值就 ok 了
import java.util.*;
import java.io.*;
/*
1. 得到连续 K 个 1 的最少相邻交换次数
给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动你可以选择 相邻 两个数字并将它们交换。
请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数。
*/
class Solution {
public int minMoves(int[] nums, int k) {
int n = nums.length;
// int[] w = new int[k];
List<Integer> lis = new ArrayList<>();
int x = 0;
for (int i = 0; i < n; i++) {
if (nums[i]==1) {
lis.add(i-x);
x++;
}
}
int[] w = lis.stream().mapToInt(Integer::valueOf).toArray();
int m = w.length;
int[] sum = new int[m+1];
for (int i = 1; i <= m; i++) {
sum[i] = sum[i-1] + w[i-1];
}
//sum[i]: [0,i-1]
int res = Integer.MAX_VALUE;
int left = 0;
for (int right = k-1; right < m; right++) {
int mid = left+(right-left)/2; //左中位数
res = Math.min(res, w[mid]*(2*mid-left-right+1)-(sum[mid+1]-sum[left])+(sum[right+1]-sum[mid+1]));
left++;
}
return res;
}
}
这里其实有一个 小的问题。比如窗口第一次向右滑动时，从 $[A_0，A_1-1，…，A_{k-1}-{k-1}]$ ，滑动到 $[A_1-1，…，A_{k-1}-{k-1}，A_{k}-k]$ 但是实际上按照我们前面的推导，这里我们需要的应该是 $[A_1，A_2-1，A_3-2，…，A_n-n]$ ，那么我们需要重新计算吗？
显然并不需要，这里两个窗口之间差距仅仅只是在坐标轴上整体的移动了一步，而我们求的是窗口内元素和中位数差值的和，对结果的计算并没有影响。
LCP 24. 数字游戏
小扣在秋日市集入口处发现了一个数字游戏。主办方共有 N 个计数器，计数器编号为 0 ~ N-1。每个计数器上分别显示了一个数字，小扣按计数器编号升序将所显示的数字记于数组 nums。每个计数器上有两个按钮，分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器，按下加一或减一按钮。
主办方请小扣回答出一个长度为 N 的数组，第 i 个元素 (0 <= i < N) 表示将 0~i 号计数器 初始 所示数字操作成满足所有条件 nums[a]+1 == nums[a+1],(0 <= a < i) 的最小操作数。回答正确方可进入秋日市集。
由于答案可能很大，请将每个最小操作数对 1,000,000,007 取余。
示例 1：
输入：nums = [3,4,5,1,6,7]
输出：[0,0,0,5,6,7]
解释：
i = 0，[3] 无需操作
i = 1，[3,4] 无需操作；
i = 2，[3,4,5] 无需操作；
i = 3，将 [3,4,5,1] 操作成 [3,4,5,6], 最少 5 次操作；
i = 4，将 [3,4,5,1,6] 操作成 [3,4,5,6,7], 最少 6 次操作；
i = 5，将 [3,4,5,1,6,7] 操作成 [3,4,5,6,7,8]，最少 7 次操作；
返回 [0,0,0,5,6,7]。
示例 2：
输入：nums = [1,2,3,4,5]
输出：[0,0,0,0,0]
解释：对于任意计数器编号 i 都无需操作。
示例 3：
输入：nums = [1,1,1,2,3,4]
输出：[0,1,2,3,3,3]
解释：
i = 0，无需操作；
i = 1，将 [1,1] 操作成 [1,2] 或 [0,1] 最少 1 次操作；
i = 2，将 [1,1,1] 操作成 [1,2,3] 或 [0,1,2]，最少 2 次操作；
i = 3，将 [1,1,1,2] 操作成 [1,2,3,4] 或 [0,1,2,3]，最少 3 次操作；
i = 4，将 [1,1,1,2,3] 操作成 [-1,0,1,2,3]，最少 3 次操作；
i = 5，将 [1,1,1,2,3,4] 操作成 [-1,0,1,2,3,4]，最少 3 次操作；
返回 [0,1,2,3,3,3]。
提示：
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^3
解法一
在补上面的题的时候看见有人提到和这题一样，所以顺便一起写一下这题，因为已经知道了和上面哪题差不多，所以这里很快就转换成和上面类似的问题了，设原来的数组为 $A_i$ 数组，转换后新数组以 $X$ 开头，则从 0~n 的转换次数为：
$$ f(n) = \sum_{i=0}^{n-1}|A_i-(X+i)| $$
我们要求的就是这个式子的最小值，这里我们将式子转换一下，设 $A_i=B_i+i$ ，那么我们的式子就变成了
$$ f(n) = \sum_{i=0}^{n-1}|B_i-X| $$
根据前面的 [结论](#104-货仓选址），很显然 $X$ 取 $B_i$ 的中位数时该式得到最小值。那么问题就转换成了如何动态的求区间的中位数，[上一题](#1703-得到连续 K 个 1 的最少相邻交换次数） 因为变化的值是下标，窗口内的下标肯定是有序的，所以直接通过左右端点就可以计算得到中位数，但是这题我们变化的是数组的值，并且是无序的，所以我们需要借助一些其他的结构，这里我采用双堆的做法动态的维护中位数，详见 数据流的中位数
有了中位数后，我们还需要滑动的过程中快速的求出上面的式子的值，这里我们再把上面的式子拆分一下就变成
$$ f(n) = \sum_{B_i \leq B_{mid}}(B_{mid}-B_{i}) + \sum_{B_i > B_{mid}}(B_i-B_{mid}) $$
左右两部分其实就对应了小于等于 $B_{mid}$ 的元素以及大于 $B_{mid}$ 的元素，我们只需要在维护双堆的同时，维护一下各个堆的元素和以及元素个数就可以快速的求出上面式子的值，时间复杂度大概 $O(NlogN)$ 的样子
import java.util.*;
import java.io.*;
class Solution {
int[] w;
//小根堆和大根堆的和
long minSum = 0l, maxSum = 0l;
//存后 1/2 小的元素
PriorityQueue<Integer> max = new PriorityQueue<>((a, b)->w[b]-w[a]);
//存前 1/2 大的元素
PriorityQueue<Integer> min = new PriorityQueue<>((a, b)->w[a]-w[b]);
//n = 10^5
public int[] numsGame(int[] nums) {
int MOD = (int)1e9+7;
int n = nums.length;
w = new int[n];
for (int i = 0; i < n; i++) {
w[i] = nums[i]-i;
}
int[] res = new int[n];
for (int i = 0; i < n; i++) {
add(i);
int mid = find();
//这里取模 WA 了两发。..int 后面没打括号，给强转了
//小根堆的个数以及 sum 代表的实际是大于 mid 的元素部分，大根堆同理
res[i] = (int)(((long)w[mid]*(max.size()-min.size()) - maxSum + minSum) % MOD);
}
return res;
}
//维护大根堆以及小根堆
public void add(int x) {
min.add(x);
minSum += w[x];
minSum -= w[min.peek()]; maxSum += w[min.peek()];
max.add(min.poll());
if (min.size() < max.size()) {
minSum += w[max.peek()]; maxSum -= w[max.peek()];
min.add(max.poll());
}
}
public int find() {
return min.peek();
}
}
public class LeetCode_LCP24 数字游戏 {
public static void main(String[] args) {
Arrays.stream(new Solution().numsGame(new int[]{3,4,5,1,6,7})).forEach(System.out::println);
}
}
122. 糖果传递
有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 1。
求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数 n，表示小朋友的个数。
接下来 n 行，每行一个整数 a[i]，表示第 i 个小朋友初始得到的糖果的颗数。
输出格式
输出一个整数，表示最小代价。
数据范围：1≤n≤1000000, 0≤a[i]≤2×109, 数据保证一定有解。
输入样例：
4
1
2
5
4
输出样例：
4
解法一
老实说，在知道这个题是绝对值不等式的题之后，我还是没有推出了正确的公式，可见我是有多菜了。
这里直接就不多写了，直接贴我 onenote 的手稿吧
代码实现如下：
import java.util.*;
import java.io.*;
class Main {
public static void main(String... args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
int N = read(br)[0];
long[] c = new long[N];
int[] A = new int[N];
long sum = 0;
for (int i = 0; i < N; i++) {
A[i] = Integer.valueOf(br.readLine());
sum += A[i];
}
long k = sum/N;
sum = 0;
for (int i = 0; i < N; i++) {
sum += A[i];
c[i] = (i+1)*k - sum;
}
Arrays.sort(c);
long res = 0;
for (int i = 0; i < N; i++) {
res += Math.abs(c[i]-c[N>>1]);
}
out.println(res);
out.flush();
}
public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}