題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🔵 AISING2020E Camel Train

Problem Statement

題目簡述

有 NN 隻駱駝排成一列。駱駝 ii 若位於最前面的 KiK_i 個位置中，幸福值為 LiL_i；否則為 RiR_i。求最大總幸福值。共有 TT 組測試資料。

Constraints

約束條件

  • 1≤T≤1051 \leq T \leq 10^5
  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5（所有測試資料的 NN 總和 ≤2×105\le 2 \times 10^5）
  • 1≤Ki≤N1 \leq K_i \leq N
  • 1≤Li,Ri≤1091 \leq L_i, R_i \leq 10^9
  • 所有輸入皆為整數

思路：反悔貪心

題型判斷

每隻駱駝有兩種可能的幸福值，取決於牠在排列中的位置是否滿足某個門檻。我們需要在排列中對每隻駱駝做出「選前方」或「選後方」的取捨，且不同駱駝的門檻值不同。這類「先選、後悔、動態調整最優集合」的結構，是反悔貪心的典型應用場景。

從暴力到核心觀察

最直觀的想法是枚舉所有 N!N! 種排列，但 NN 可以到 2×1052\times 10^5，完全不可行。我們需要從問題結構中尋找可以簡化的性質。

引導思考

對於兩隻駱駝 ii 和 jj，如果 Li>RiL_i > R_i（偏好前方）而 Lj<RjL_j < R_j（偏好後方），在任意排列中，讓誰站在前面更有利？

核心觀察：交換論證

考慮兩隻駱駝 ii 和 jj。如果 Li>RiL_i > R_i（駱駝 ii 偏好前方）而 Lj≤RjL_j \le R_j（駱駝 jj 偏好後方），那麼在任意排列中，若駱駝 jj 排在駱駝 ii 前面，將兩者交換不會使總幸福值變差。

直覺解釋：偏好前方的駱駝站在前面能拿到更大的值，偏好後方的駱駝站在後面能拿到更大的值。把偏好前方的往前挪、偏好後方的往後挪，兩者各得其所，整體只會更好。

因此，所有 L>RL > R 的駱駝應該排在 L≤RL \le R 的駱駝前面。兩組之間互不干擾，問題可以拆成兩個獨立的子問題。

可遷移套路：交換論證

當你需要確定元素的相對順序時，考慮交換相鄰兩元素，觀察目標函數的變化。如果交換後不會更差，就能推導出一個偏序關係。

問題分解

根據上述觀察，將駱駝分成獨立的兩組：

  • 前方組（Li>RiL_i > R_i）：傾向站在前方。基礎貢獻先取 RiR_i，若成功排入前 KiK_i 名，則額外獲得差值 Li−RiL_i - R_i。
  • 後方組（Li≤RiL_i \le R_i）：傾向站在後方。基礎貢獻先取 LiL_i，若成功排在後 N−KiN-K_i 名（即不在前 KiK_i 名），則額外獲得差值 Ri−LiR_i - L_i。

兩組的計算方式完全對稱，下面以前方組為例做詳細推導。

前方組：反悔貪心的推導

對於前方組的駱駝，基礎幸福值（所有 RiR_i）已經全部算入答案。現在的實質問題是：

在最多只能選 KiK_i 隻駱駝排入「前 KiK_i 名」的限制下，如何選取差值 Li−RiL_i - R_i，使額外收益最大？

注意這裡的限制因駱駝而異——門檻值 KiK_i 大的容易滿足，小的競爭激烈。

關鍵轉換：排序後門檻逐步放寬

將前方組駱駝按 KiK_i 從小到大排序。當我們處理到門檻值為 KK 的駱駝時，最多只能有 KK 隻駱駝被選入前方。隨著 KK 增加，容量在逐步放寬。

這直接引出反悔貪心的策略：

  1. 按門檻值 KiK_i 從小到大處理每隻駱駝。
  2. 對於當前駱駝，先「貪心」地將它的差值選入（加入一個最小堆積）。
  3. 若選入後，已選數量超過當前的門檻值 KK，則從堆積中彈出最小的差值——捨棄之前最不划算的選擇，即「反悔」。
為什麼是最小堆積？

當容量超限、必須捨棄時，最優策略是捨棄貢獻最小的那一個。最小堆積能在 O(log⁡N)O(\log N) 時間內找出並移除最小值。

排序方向

前方組必須按 KiK_i 遞增排序——門檻值越小限制越嚴格，必須優先處理。如果反過來按遞減排，會出現「早期選太多、後期才發現容量不夠」的情況，無法正確回退。

處理完所有駱駝後，堆積中剩餘的元素就是最終被選入前方的差值，全部加入答案。

後方組：對稱處理

後方組的邏輯與前方組完全對稱。基礎貢獻取 LiL_i，額外收益為 Ri−LiR_i - L_i（注意此時 Ri≥LiR_i \ge L_i，差值非負）。

關鍵差異在於：後方組的駱駝需要排在「後 N−KiN-K_i 名」。也就是說，對於門檻值為 KiK_i 的駱駝，最多只能有 N−KiN-K_i 隻後方組駱駝被選入後方。

處理方式：

  • 按 KiK_i 遞減排序（等價於按剩餘空位 N−KiN-K_i 從小到大）。
  • 已選數量超過 N−KN-K 時，彈出最小差值。
本題要點

核心技巧是交換論證將問題分解為兩個獨立子問題，以及反悔貪心處理帶有不同限制條件的選擇問題。關鍵在於將「每個元素有不同的門檻」透過排序轉化為「逐步放寬的容量限制」，再用堆積動態維護最優選擇集。

複雜度分析

  • 時間複雜度：O(Nlog⁡N)\mathcal{O}(N \log N) — 每組測試資料需要排序（O(Nlog⁡N)\mathcal{O}(N \log N)）以及對每隻駱駝進行一次堆積操作（O(log⁡N)\mathcal{O}(\log N)）。
  • 空間複雜度：O(N)\mathcal{O}(N) — 需要儲存分組後的駱駝差值，以及堆積的大小。

Code

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
46
47
48
49
50
from heapq import heappush, heappushpop
from collections import defaultdict


def solve():
    n = int(input())

    # 按門檻值 K 分組儲存差值（前方組 L-R，後方組 R-L）
    A = defaultdict(list)
    B = defaultdict(list)

    ans = 0
    for _ in range(n):
        k, l, r = map(int, input().split())
        if l > r:
            ans += r               # 前方組基礎貢獻取 R
            A[k].append(l - r)     # 若成功排入前方，可額外獲得 L-R
        else:
            ans += l               # 後方組基礎貢獻取 L
            B[k].append(r - l)     # 若成功排入後方，可額外獲得 R-L

    # 前方組：按 K 遞增，用最小堆積維護已選差值
    hp = []
    for k, ds in sorted(A.items()):          # K 從小到大
        for d in ds:
            ans += d                          # 先計入差值
            if len(hp) < k:
                heappush(hp, d)               # 容量未滿，直接選入
            else:
                # 容量已滿：heappushpop 推入 d 並彈出最小，只保留前 k 大
                ans -= heappushpop(hp, d)

    # 後方組：按 K 遞減，對稱處理（容量為 N-K）
    hp = []
    for k, ds in sorted(B.items(), reverse=True):  # K 從大到小
        k = n - k                                   # 轉換為後方容量
        for d in ds:
            ans += d
            if len(hp) < k:
                heappush(hp, d)
            else:
                ans -= heappushpop(hp, d)

    print(ans)


if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()