发表更新基础 / 模板17 分钟读完 (大约2551个字)

排序算法

本文内容参考 sorting-algorithms，《算法》，《算法导论》。（强迫症，最后还是把描述性的文字删了，只贴代码）

验证算法的正确性，可以使用：912. 排序数组，148. 排序链表，164. 最大间距。

简单概述

理想的排序算法

  • 稳定性：相同键不会重新排序。
  • 原地排序：不使用额外空间存储排序数据。
  • 最坏情况 \(O(n\log{n})\) 次比较，\(O(n)\) 次交换。
  • 适应性：当数据接近排序或唯一键很少时，时间复杂度为 \(O(n)\)。

如何看待常数因子的改进方案

摘抄自《算法》的一段内容：在每一节中，我们会将书中的每个算法都看做某种应用的关键。但在整体上，我们希望学习的是为每种应用找到最合适的算法。我们并不是在推荐读者一定要实现所有提到的改进方法，而是提醒大家不要对算法初始实现的性能盖棺定论。研究一个新问题时，最好的方法是先实现一个你能想到的最简单的程序，当它成为瓶颈的时候再继续改进它。实现那些只能把运行时间缩短某个常数因子的改进措施可能并不值得。你需要用实验来检验一项改进，正如本书练习所演示的那样。

冒泡排序

  • 稳定性：稳定。
  • 时间复杂度：\(O(n^{2})\)。
  • 空间复杂度：\(O(1)\)。
  • 数据接近排序时，时间复杂度为 \(O(n)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static void bubbleSort(int[] nums) {
    int n = nums.length, pos;
    for (int i = n - 1; i > 0; i = pos) {
        pos = 0;
        for (int j = 0; j < i; j++) {
            // 稳定性的关键
            if (nums[j] > nums[j + 1]) {
                swap(nums, j, j + 1);
                // 将最后交换的位置，作为下次冒泡的上界
                pos = j;
            }
        }
    }
}

选择排序

  • 稳定性：不稳定。
  • 时间复杂度：\(O(n^{2})\)。元素的交换次数最少的排序算法。
  • 空间复杂度：\(O(1)\)。
1
2
3
4
5
6
7
8
9
10
11
12
private static void selectionSort(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) swap(nums, minIndex, i);
    }
}

插入排序

  • 稳定性：稳定。
  • 时间复杂度：\(O(n^{2})\)。元素的交换次数等于逆序数。
  • 空间复杂度：\(O(1)\)。
  • 数据接近排序时，时间复杂度为 \(O(n)\)。
1
2
3
4
5
6
7
8
9
10
11
private static void insertionSort(int[] nums) {
    int n = nums.length;
    for (int i = 1; i < n; i++) {
        int j = i - 1, t = nums[i];
        // 稳定性的关键
        for (; j >= 0 && nums[j] > t; j--) {
            nums[j + 1] = nums[j];
        }
        nums[j + 1] = t;
    }
}

希尔排序

  • 稳定性：不稳定。
  • 时间复杂度：使用 Knuth 增量序列 \(O(n^{\frac{3}{2}})\)，。Knuth 增量序列：\(1,4,13,40,\dots,\frac{3^{k}-1}{2}\)，相当于首项为 \(1\)，公比为 \(3\) 的数列的前缀和。
  • 空间复杂度：\(O(1)\)。
  • 数据接近排序时，时间复杂度为 \(O(n\log{n})\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static void insertionSort(int[] nums) {
    int n = nums.length, h = 1;
    while (h < n / 3) h = 3 * h + 1;
    while (h >= 1) {
        for (int i = h; i < n; i++) {
            int j = i - h, t = nums[i];
            for (; j >= 0 && nums[j] > t; j -= h) {
                nums[j + h] = nums[j];
            }
            nums[j + h] = t;
        }
        h /= 3;
    }
}

归并排序

  • 稳定性：稳定的。
  • 时间复杂度：\(O(n\log{n})\)。
  • 空间复杂度：排序数组 \(O(n)\)；自顶向下排序链表 \(O(\log{n})\)（递归的空间），自底向上排序链表 \(O(1)\)。
  • 顺序访问数据，缓存友好。

实现一：自顶向下（数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
private static void mergeSort(int[] nums) {
    int n = nums.length;
    int[] aux = new int[n];
    mergeSort(nums, aux, 0, n - 1);
}

private static void mergeSort(int[] nums, int[] aux, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(nums, aux, lo, mid);
    mergeSort(nums, aux, mid + 1, hi);
    merge(nums, aux, lo, mid, hi);
}

private static void merge(int[] nums, int[] aux, int lo, int mid, int hi) {
    for (int i = lo; i <= hi; i++) {
        aux[i] = nums[i];
    }
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) nums[k] = aux[j++];
        else if (j > hi) nums[k] = aux[i++];
        // 稳定性的关键
        else if (aux[i] <= aux[j]) nums[k] = aux[i++];
        else nums[k] = aux[j++];
    }
}

实现二：自底向上（数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static void mergeSort(int[] nums) {
    int n = nums.length;
    int[] aux = new int[n];
    for (int len = 1; len < n; len += len) {
        for (int i = 0; i + len < n; i += len << 1) {
            merge(nums, aux, i, i + len - 1, Math.min(n - 1, i + (len << 1) - 1));
        }
    }
}

private static void merge(int[] nums, int[] aux, int lo, int mid, int hi) {
    for (int i = lo; i <= hi; i++) {
        aux[i] = nums[i];
    }
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) nums[k] = aux[j++];
        else if (j > hi) nums[k] = aux[i++];
        // 稳定性的关键
        else if (aux[i] <= aux[j]) nums[k] = aux[i++];
        else nums[k] = aux[j++];
    }
}

实现三：自顶向下（链表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
private static ListNode mergeSort(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    // 分为两个子链表
    ListNode mid = middleNode(head);
    ListNode next = mid.next;
    mid.next = null;

    head = mergeSort(head);
    next = mergeSort(next);
    return merge(head, next);
}

// 返回合并链表的头节点
private static ListNode merge(ListNode head1, ListNode head2) {
    ListNode dummy = new ListNode(), curr = dummy;
    while (head1 != null && head2 != null) {
        // 稳定性的关键
        if (head1.val <= head2.val) {
            curr.next = head1;
            head1 = head1.next;
        } else {
            curr.next = head2;
            head2 = head2.next;
        }
        curr = curr.next;
    }
    curr.next = head1 != null ? head1 : head2;
    return dummy.next;
}

// 调用保证 head != null，并且如果有两个中间节点，则返回前一个（不然会无限递归）
// 使用 fast = head.next 可以保证返回前一个中间节点
// 使用 fast = head 可以保证返回后一个中间节点
private static ListNode middleNode(ListNode head) {
    if (head == null) return head;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

实现四：自底向上（链表）

下面这个是没有提前计算链表长度，没有断开链表的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
private static ListNode mergeSort(ListNode head) {
    if (head == null || head.next == null) return head;

    int len = 1;
    ListNode dummy = new ListNode(-1, head);

    while (true) {
        // 两个子链表的头节点的前一个节点
        ListNode prev1, prev2;
        prev1 = prev2 = dummy;
        while (true) {
            for (int i = 0; i < len && prev2 != null; i++) {
                prev2 = prev2.next;
            }
            if (prev2 == null || prev2.next == null) break;

            prev1 = prev2 = merge(prev1, prev2, len);
        }
        // 如果该轮没有进行合并操作，则排序完成
        if (prev1 == dummy) break;
        len += len;
    }
    return dummy.next;
}

// 返回合并链表的尾节点
private static ListNode merge(ListNode prev1, ListNode prev2, int len) {
    // 判断条件：第一个链表未结束 && 第二个链表未结束（考虑长度不足的情况）
    while (prev1 != prev2 && len != 0 && prev2.next != null) {
        // 稳定性的关键
        if (prev1.next.val > prev2.next.val) {
            // 将 prev2.next 插入到 prev1 之后
            ListNode temp = prev2.next;
            prev2.next = prev2.next.next;
            temp.next = prev1.next;
            prev1.next = temp;
            len--;
        }
        prev1 = prev1.next;
    }
    // 使 prev2 指向合并链表的尾节点
    while (len-- != 0 && prev2.next != null) prev2 = prev2.next;
    return prev2;
}

快速排序

  • 稳定性：不稳定。
  • 时间复杂度：期望 \(O(n\log{n})\)。
  • 空间复杂度：期望 \(O(\log{n})\)。
  • 如果使用三路快排，数据包含大量重复元素时，时间复杂度为 \(O(n)\)。

实现一：二路快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
private static void quickSort(int[] nums) {
    int n = nums.length;
    quickSort(nums, 0, n - 1);
}

private static void quickSort(int[] nums, int lo, int hi) {
    if (lo >= hi) return;
    int index = partition(nums, lo, hi);
    quickSort(nums, lo, index - 1);
    quickSort(nums, index + 1, hi);
}

private static int partition(int[] nums, int lo, int hi) {
    // 三数取中
    int mid = median3(nums, lo, lo + (hi - lo) / 2, hi);
    swap(nums, lo, mid);
    
    int key = nums[lo];
    int i = lo, j = hi + 1;
    while (true) {
        // 和切分元素相等的元素也会停顿并交换
        while (nums[++i] < key && i != hi);
        while (nums[--j] > key);
        if (i >= j) break;
        swap(nums, i, j);
    }
    swap(nums, lo, j);
    return j;
}

实现二：三路快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private static final Random RANDOM = new Random();

private static void quickSort(int[] nums) {
    int n = nums.length;
    quickSort(nums, 0, n - 1);
}

private static void quickSort(int[] nums, int lo, int hi) {
    if (lo >= hi) return;

    // 随机选择
    int randomIndex = lo + RANDOM.nextInt(hi - lo + 1);
    swap(nums, randomIndex, lo);

    int key = nums[lo];
    int lt = lo, gt = hi, i = lo + 1;
    while (i <= gt) {
        if (nums[i] < key) swap(nums, i++, lt++);
        else if (nums[i] > key) swap(nums, i, gt--);
        else i++;
    }

    quickSort(nums, lo, lt - 1);
    quickSort(nums, gt + 1, hi);
}

堆排序

  • 稳定性：不稳定。
  • 时间复杂度：\(O(n\log{n})\)。
  • 空间复杂度：\(O(1)\)。
  • 随机访问数据，缓存不友好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static void heapSort(int[] nums) {
    int n = nums.length;

    // 建堆 - 时间复杂度 O(n)
    for (int i = n / 2 - 1; i >= 0; i--) {
        sink(nums, i, n - 1);
    }

    // 排序 - 时间复杂度 O(nlog(n))
    for (int i = n - 1; i > 0; ) {
        swap(nums, 0, i--);
        sink(nums, 0, i);
    }
}

private static void sink(int[] nums, int i, int n) {
    int t = nums[i];
    while (2 * i + 1 <= n) {
        int j = 2 * i + 1;
        if (j + 1 <= n && nums[j + 1] > nums[j]) {
            j++;
        }
        if (t >= nums[j]) break;
        nums[i] = nums[j];
        i = j;
    }
    nums[i] = t;
}

计数排序

  • 稳定性：稳定。
  • 时间复杂度：\(O(n+k)\)。
  • 空间复杂度：\(O(n+k)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 元素取值范围 [0,k)
private static int[] countingSort(int[] nums, int k) {
    int n = nums.length;
    int[] cnt = new int[k];
    int[] res = new int[n];

    // 计数
    for (int x : nums) {
        cnt[x]++;
    }

    // 前缀和
    for (int i = 1; i < k; i++) {
        cnt[i] += cnt[i - 1];
    }

    // 排序（倒序遍历，保证稳定性）
    for (int i = n - 1; i >= 0; i--) {
        res[--cnt[nums[i]]] = nums[i];
    }
    return res;
}

基数排序

  • 稳定性：稳定。
  • 时间复杂度：\(O(d\cdot (n+k))\)。
  • 空间复杂度：\(O(n+k)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 元素最多有 d 位
private static int[] radixSort(int[] nums, int d) {
    int n = nums.length;
    int[] cnt = new int[10];
    int[] aux = new int[n];
    int divisor = 1;
    for (int i = 0; i < d; i++) {
        countingSort(nums, cnt, aux, divisor);
        
        Arrays.fill(cnt, 0);
        divisor *= 10;
        
        int[] t = nums;
        nums = aux;
        aux = t;
    }
    return nums;
}

private static void countingSort(int[] nums, int[] cnt, int[] aux, int divisor) {
    int n = nums.length;

    // 计数
    for (int x : nums) {
        cnt[x / divisor % 10]++;
    }

    // 前缀和
    for (int i = 1; i < 10; i++) {
        cnt[i] += cnt[i - 1];
    }

    // 排序（倒序遍历，保证稳定性）
    for (int i = n - 1; i >= 0; i--) {
        aux[--cnt[nums[i] / divisor % 10]] = nums[i];
    }
}

桶排序

  • 稳定性：取决于桶内的排序策略。
  • 时间复杂度：期望 \(O(n)\)。（输入数据均匀分布时）
  • 空间复杂度：\(O(n+m)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
private static void bucketSort(int[] nums) {
    int n = nums.length;

    if (n <= 1) return;

    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int x : nums) {
        min = Math.min(min, x);
        max = Math.max(max, x);
    }

    // 小心除以零
    int inter = Math.max(1, (max - min) / (n - 1));
    int bucketSize = (max - min) / inter + 1;

    List<Integer>[] buckets = new List[bucketSize];
    Arrays.setAll(buckets, k -> new ArrayList<>());

    for (int x : nums) {
        int i = (x - min) / inter;
        buckets[i].add(x);

        // 插入排序
        int j = buckets[i].size() - 1;
        for (; j > 0 && buckets[i].get(j - 1) > x; j--) {
            buckets[i].set(j, buckets[i].get(j - 1));
        }
        buckets[i].set(j, x);
    }

    int idx = 0;
    for (var bucket : buckets) {
        for (int x : bucket) {
            nums[idx++] = x;
        }
    }
}
发表更新基础 / 模板8 分钟读完 (大约1252个字)

动态规划

本文内容参考《算法导论》，OI Wiki。

基础知识

动态规划方法通常用来求解最优化问题。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。

适合应用动态规划方法求解的最优化问题应该具备两个要素：最优子结构和重叠子问题。

  • 最优子结构：问题的最优解由相关子问题的最优解组合而成，而这些子问题可以独立求解。
  • 重叠子问题：如果问题的递归算法会反复求解相同的子问题，我们就称最优化问题具有重叠子问题性质。

子问题图

子问题图是一个有向图，每个顶点唯一的对应一个子问题。若求子问题 \(x\) 的最优解时需要直接用到子问题 \(y\) 的最优解，那么在子问题图中就会有一条从子问题 \(x\) 的顶点到子问题 \(y\) 的顶点的有向边。

自顶向下动态规划处理子问题图中顶点的顺序为拓扑序，自底向上动态规划处理子问题图中顶点的顺序为逆拓扑序。

通常情况下，动态规划算法的运行时间与子问题图中顶点和边的数量呈线性关系。

选择自顶向下，还是自底向上

通常情况下，如果每个子问题都必须至少求解一次，自底向上动态规划算法会更快，因为没有递归调用的开销，而且对于某些问题，可以利用表的访问模式降低时空开销。如果子问题空间中的某些子问题完全不必求解，自顶向下动态规划算法会更快，因为它只会求解那些必要的子问题。

背包 DP

题目：有 \(n\) 种物品和一个容量为 \(W\) 的背包，每种物品有数量 \(k_{i}\)、重量 \(w_{i}\) 和价值 \(v_{i}\) 三种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

0-1 背包

每种物品只能取一次，即 \(k_{i}=1\) 对任意 \(i\) 都成立。

转移方程：

$$ dp[i][j]=\max{(dp[i-1][j],dp[i-1][j-w[i]]+v[i])} $$

空间优化（倒序枚举）：

$$ dp[j]=\max{(dp[j],dp[j-w[i]]+v[i])} $$

完全背包

每种物品可以取无限次，即 \(k_{i}=\infty\) 对任意 \(i\) 都成立。

转移方程：

$$ dp[i][j]=\max_{k=0}^{\infty}{dp[i-1][j-k\cdot w[i]]+k\cdot v[i]} $$

方程优化：

$$ dp[i][j]=\max{(dp[i-1][j],dp[i][j-w[i]]+v[i])} $$

空间优化（正序枚举）：

$$ dp[j]=\max(dp[j],dp[j-w[i]]+v[i]) $$

多重背包

每种物品可以取 \(k_{i}\) 次，即 \(k_{i}\in\mathbb{N}\) 对任意 \(i\) 都成立。

转移方程：

$$ dp[i][j]=\max_{k=0}^{k[i]}{dp[i-1][j-k\cdot w[i]]+k\cdot v[i]} $$

二进制分组优化：将每种物品的 \(k_{i}\) 拆分为多个组，每组的数量为 \(2^{0},2^{1},\dots,2^{\lfloor{\log{k_{i}+1}}\rfloor -1}\)，如果 \(k_{i}+1\) 不是二的幂，就将多余的数量作为一组，最后将 \(k_{i}\) 拆出来的每组都看作数量为 \(1\) 的新物品，从而转化为 0-1 背包。可以证明，如果选择 \(x\) 次第 \(i\) 种物品，其中 \(x\in[0,k_{i}]\)，则该选择方式总是可以由分组后的新物品的某个组合表示。

例题

发表更新算法 / Codeforces6 分钟读完 (大约898个字)

Codeforces Round 905 (Div. 2)

Chemistry

只要奇数字母的个数不大于 \(k+1\) 即可，因为回文串最多有一个奇数字母。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    String s = io.next();

    int[] cnt = new int[26];
    for (int i = 0; i < n; i++) {
        cnt[s.charAt(i) - 'a']++;
    }

    int sum = 0;
    for (int x : cnt) {
        if (x % 2 == 1) {
            sum++;
        }
    }
    io.println(sum - 1 > k ? "NO" : "YES");
}

Raspberries

当 \(k=2,3,5\) 时，因为 \(k\) 是质数，如果所有数的乘积能够被 \(k\) 整除，必定存在一个数能够被 \(k\) 整除，所以单独计算每个数即可。当 \(k=4\) 时，需要计算存在一个数能被 \(4\) 整除的最少操作数，还需要计算存在两个能被 \(2\) 整除的数的最少操作数，答案为两者的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();

    int cnt = 0;
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        if (a[i] % 2 == 0) {
            cnt++;
        }
    }

    int ans = k;
    for (int i = 0; i < n; i++) {
        ans = Math.min(ans, (k - a[i] % k) % k);
    }
    if (k == 4) {
        ans = Math.min(ans, Math.max(0, 2 - cnt));
    }
    io.println(ans);
}

You Are So Beautiful

如果某个子数组作为子序列只出现过一次，因为子数组本身就是子序列，所以没有其他方式能够构成该子数组，即子数组的左端点左边没有和它相同的数，右端点的右边也没有和它相同的数。我们可以使用集合 + 前缀和的方式预先计算每个位置及其左边满足条件的左端点个数，然后倒序处理数组，对每个满足条件的右端点，都将其对应的左端点的个数添加到答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }

    Set<Integer> set = new HashSet<>();
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + (set.add(a[i]) ? 1 : 0);
    }
    set.clear();

    long ans = 0L;
    for (int i = n - 1; i >= 0; i--) {
        if (set.add(a[i])) {
            ans += prefix[i + 1];
        }
    }
    io.println(ans);
}

Dances (Easy version)

题目真难读，简单版只会在数组 \(a\) 中添加一个 \(1\)，然后计算最少操作数，可以使用排序 + 双指针进行处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] a = new int[n];
    a[0] = 1;
    for (int i = 1; i < n; i++) {
        a[i] = io.nextInt();
    }
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
    }

    Arrays.sort(a);
    Arrays.sort(b);

    int k = 0;
    for (int i = 0, j = 0; i < n - k; i++, j++) {
        while (j < n && a[i] >= b[j]) {
            k++;
            j++;
        }
    }
    io.println(k);
}

Dances (Hard Version)

困难版，计算在数组中分别添加 \([1,m]\) 需要的最少操作数。通过观察可以发现（真发现不了），改变 \(a[0]\) 最多只会使操作次数加 \(1\)，所以我们可以二分该边界值，然后计算答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] a = new int[n];
    for (int i = 1; i < n; i++) {
        a[i] = io.nextInt();
    }
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
    }
    Arrays.sort(b);

    int k = calc(a, b, 1);

    int lo = 1, hi = m;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (calc(a, b, mid) == k) lo = mid + 1;
        else hi = mid - 1;
    }
    io.println((long) m * k + (m - lo + 1));
}

private static int calc(int[] a, int[] b, int x) {
    a[0] = x;
    a = a.clone();
    Arrays.sort(a);

    int n = a.length, k = 0;
    for (int i = 0, j = 0; i < n - k; i++, j++) {
        while (j < n && a[i] >= b[j]) {
            k++;
            j++;
        }
    }
    return k;
}

竟然还有更简单的方法，首先计算 \(a\) 中 \(n-1\) 个数对应 \(b\) 中 \(n\) 个数的最少删除次数，并同时维护 \(b\) 中不满足 \(a[i]<b[j]\) 的最后一个值，该值就是操作次数的分界点，直接计算答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] a = new int[n];
    a[0] = Integer.MAX_VALUE;
    for (int i = 1; i < n; i++) {
        a[i] = io.nextInt();
    }
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
    }

    Arrays.sort(a);
    Arrays.sort(b);

    int k = 0, val = m + 1;
    for (int i = 0, j = 0; i < n - k; i++, j++) {
        while (j < n && a[i] >= b[j]) {
            val = b[j];
            k++;
            j++;
        }
    }
    io.println((long) m * (k - 1) + Math.max(0, m - val + 1));
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×