ACD 1216 Beautiful People：二維 LIS 最長遞增子序列

ACD 1216 Beautiful People：二維 LIS 最長遞增子序列

題目大意

N (≤100,000) 人，每人屬性 S, B。若 S1S2 且 B1>B2 則不互討厭。求最大子集使任意兩人不互討厭。

轉化為二維 LIS

• 按 S 升序排序，S 相同按 B 降序（關鍵：避免相同 S 被誤判為遞增）
• 對排序後的 B 序列求嚴格遞增最長子序列 (LIS)
• LIS 長度即為答案

O(N log N) LIS 算法

維護 dp[len] = 長度為 len 的遞增子序列最小末尾值。
對每個 B，二分查找第一個 ≥ B 的位置替換，或追加。
同時記錄前驅重構路徑。

完整代碼

#include 
#include 
#include 
using namespace std;

const int MAXN = 100010;
struct Person { int id, S, B;
    bool operator<(const Person& o) const {
        return S < o.S || (S == o.S && B > o.B);
    }
} p[MAXN];

int buf[MAXN], dp[MAXN], pre[MAXN], pos[MAXN];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &p[i].S, &p[i].B);
            p[i].id = i;
        }
        sort(p+1, p+n+1);
        for (int i = 1; i <= n; ++i) buf[i] = p[i].B;

        memset(dp, 0x3f, sizeof(dp));
        memset(pre, -1, sizeof(pre));
        int len = 0;
        for (int i = 1; i <= n; ++i) {
            int k = lower_bound(dp+1, dp+len+1, buf[i]) - dp;
            dp[k] = buf[i];
            pre[i] = pos[k-1];
            pos[k] = i;
            if (k > len) len = k;
        }
        printf("%d ", len);
        // 重構輸出路徑（略）
        puts("");
    }
    return 0;
}

關鍵點

• 排序策略：S 升、B 降 → 保證 LIS 中不會選到相同 S 的人
• lower_bound 求嚴格遞增（≥ 替換）
• 記錄 pos[len] 和 pre[i] 可重構具體方案
• N=10⁵，O(N log N) 必須

此題是「二維偏序 → 排序 + 一維 LIS」的教科書級應用。