同花顺

题目解析

题目要求“最少更换多少张牌”，我们可以运用逆向思维：

\text{最少更换数} = \text{总牌数 } n - \text{最多能保留的牌数}

所以，问题转化成了：在 $n$ 张牌中，最多能找出多少张牌，使得它们属于同一种花色，且数字可以包含在一个长度为 $n$ 的连续区间内。

4个花色存在4个 vector 里, 每个花色单独做(这里有误,题目的花色不止4种) 显然是枚举, 固定结尾j, 问j 最多能配对多少个牌(数字可以包含在一个长度为n的区间内, a[j] - a[i] <= n-1) 双指针或者单调队列 ,或二分

将 4 种花色分开处理

我们真正需要的是：在一个有序数组中，找出一个最长的子段，使得子段内 最大值 - 最小值 <= n - 1。

用 std::vector 分开存储 + std::upper_bound (二分查找) 来代替双指针，代码会非常优雅。

解释: 最大值 - 最小值 <= n - 1

这是用 “相框模型” 最直观的解释：

1. 想象一个固定大小的相框

想象你有一个 长度为 $n$ 的相框。这个相框正好有 $n$ 个格子，每个格子只能放一张牌。

2. 规则：能被“框住”才能保留

你想保留的一组牌，必须能同时被这个相框框住。

如果牌太分散，超过了相框的长度，相框就盖不住它们了。

3. 为什么是 $n-1$ ？

我们来看相框的内部距离：

相框的第 $1$ 个格子，和第 $n$ 个格子（最后一个格子），中间隔了多少步？
- 答案是： $n - 1$ 步。
- 就像你有 5 个手指（ $n=5$ ），但只有 4 个指缝（ $n-1=4$ ）。

4. 结论

如果你选的 最大牌 (Max) 和 最小牌 (Min) 之间的距离超过了 $n-1$ ，说明它们离得太远了：

Max - Min > $n-1$ $\rightarrow$ 相框不够长（首尾够不着），必须扔掉其中一张。
Max - Min $\le$ $n-1$ $\rightarrow$ 相框够长，可以把它们都框进去，中间缺的牌补上就行。

代码思路

离散化 正是为了解决“数值很大（ $10^9$ ），但有效数据很少（ $10^5$ ）”导致无法使用数组下标的问题。

通过离散化花色，我们可以把 $10^9$ 范围的花色映射到 $0 \sim N-1$ 的小整数范围，这样就可以重新使用 vector<int> piles[N] 这种高效的数组结构

核心步骤

收集：读入时，把所有花色存入一个临时数组 alls。
离散化模板操作：对 alls 进行 sort 和 unique。
映射：使用 lower_bound 算出每个原始花色对应的“排名”（ID）。
分桶：用这个 ID 作为数组下标，把牌放入对应的 vector 中。
独立处理：对每个 vector 进行单独计算，取最大值。
核心逻辑：
- 排序 + 去重。
- 遍历每个数字 $x$ 作为同花顺的起点。
- 同花顺的理论终点应该是 $x + n - 1$ 。
- 用 upper_bound 快速找出第一个大于终点的数字位置。
- 两个下标一减，就是在 $n$ 范围内的牌的数量。

复杂度

时间：排序 $O(N \log N)$ + 遍历查找 $O(N \log N)$ 。总复杂度依然是 $O(N \log N)$ ，可以通过 $10^5$ 的数据。
空间： $O(N)$

代码

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100005;

// 存储原始输入的牌，方便后续处理
struct CardInput {
    int suit, num;
};
vector<CardInput> inputs;

// 离散化数组：存储所有出现过的花色
vector<int> all_suits;

// 核心容器：piles[i] 存储第 i 种花色下的所有数字
// 此时 i 的范围是 0 ~ N，不再是 10^9
vector<int> piles[N]; 

int n;

// --- 离散化辅助函数 ---
// 传入原始花色，返回离散化后的 ID (0, 1, 2...)
int get_suit_id(int original_suit) {
    // lower_bound 查找第一个 >= x 的位置
    return lower_bound(all_suits.begin(), all_suits.end(), original_suit) - all_suits.begin();
}

// --- 核心逻辑 (和之前一样) ---
int solve_suit(vector<int>& v) {
    if (v.empty()) return 0;
    
    // 1. 排序
    sort(v.begin(), v.end());
    // 2. 去重
    v.erase(unique(v.begin(), v.end()), v.end());
    
    int max_len = 0;
    
    // 3. 遍历 + upper_bound
    for (int i = 0; i < v.size(); i++) {
        // 目标：找到以 v[i] 为起点，数值在 [v[i], v[i] + n - 1] 范围内的最远位置
        // 注意：这里 v[i] + n - 1 可能会超过 int 范围，但这题 max val 是 10^9，加 10^5 不会爆 int
        int end_limit = v[i] + n - 1;
        
        // 找第一个 大于 end_limit 的位置
        auto it = upper_bound(v.begin(), v.end(), end_limit);
        
        int count = (it - v.begin()) - i;
        max_len = max(max_len, count);
    }
    
    return max_len;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n)) return 0;
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    // 1. 读入数据并收集花色
    inputs.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> inputs[i].suit >> inputs[i].num;
        all_suits.push_back(inputs[i].suit);
    }

    // 2. 离散化处理 (Sort + Unique)
    sort(all_suits.begin(), all_suits.end());
    all_suits.erase(unique(all_suits.begin(), all_suits.end()), all_suits.end());

    // 3. 数据分发 (使用离散化后的 ID)
    for (int i = 0; i < n; i++) {
        // 将原始花色转为小整数 ID
        int id = get_suit_id(inputs[i].suit);
        // 放入对应的桶
        piles[id].push_back(inputs[i].num);
    }

    // 4. 计算答案
    int max_keep = 0;
    // all_suits.size() 就是实际有多少种不同的花色
    for (int i = 0; i < all_suits.size(); i++) {
        max_keep = max(max_keep, solve_suit(piles[i]));
    }

    cout << n - max_keep << endl;

    return 0;
}

思路2

还可以这样 ,直接按花色排序, 花色相同的从小到大排序, 每次处理一个花色的牌(一个区间内),只使用一个 vector ,来存牌, 然后在这个vector上,进行二分查找

这是最节省空间且逻辑最顺畅的写法。

利用了 排序 (Sort) 的特性：只要按“花色第一关键字、数字第二关键字”排序，相同花色的牌自然会聚在一起，并且数字已经是通过排序有序的了。

这样我们就不需要开 map，也不需要开 $N$ 个 vector 数组，只需要一个临时 vector 反复利用即可。

核心逻辑

全局排序：让所有牌排好队，花色相同的在一起，数字也从小到大。
双指针分组：用一个循环找到当前花色的 start 和 end 下标。
提取处理：把这一个区间的数字放入 vector（此时天然有序），去重，算二分。
清空复用：处理完当前花色，清空 vector，处理下一组。

这个版本的优点

极度省内存：
- 不需要 map 节点开销。
- 不需要 piles[N] 这种大数组。
- 只有一个 cur_nums，最大长度也不会超过 $N$ ，用完就清空，内存反复横跳利用。
速度优化：
- 利用了全局 sort 的结果，在 solve() 函数内部省去了一次 sort。虽然总复杂度还是 $O(N \log N)$ ，但常数小了很多。
代码结构清晰：
- 这就是典型的 “分组循环” (Grouping Loop) 写法，是处理序列分段问题的标准模板。

代码

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100005;

struct Card {
    int suit;
    int num;

    // 重载小于号：优先按花色排，花色相同按数字排
    bool operator<(const Card& other) const {
        if (suit != other.suit) return suit < other.suit;
        return num < other.num;
    }
};

Card cards[N];
int n;

// 复用的临时容器，避免反复申请内存
vector<int> cur_nums;

// 核心计算函数 (对当前这一种花色进行处理)
int solve() {
    if (cur_nums.empty()) return 0;
    
    // 注意：因为外部 cards 已经排过序了，
    // 所以 push 进来的数字天然是有序的，不需要再 sort！
    
    // 1. 去重
    cur_nums.erase(unique(cur_nums.begin(), cur_nums.end()), cur_nums.end());
    
    int max_len = 0;
    
    // 2. 二分查找逻辑
    for (int i = 0; i < cur_nums.size(); i++) {
        int end_limit = cur_nums[i] + n - 1;
        
        // 找到第一个大于 end_limit 的位置
        auto it = upper_bound(cur_nums.begin(), cur_nums.end(), end_limit);
        
        int count = (it - cur_nums.begin()) - i;
        max_len = max(max_len, count);
    }
    return max_len;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    if (!(cin >> n)) return 0;
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 0; i < n; i++) {
        cin >> cards[i].suit >> cards[i].num;
    }

    // 1. 全局排序 (关键步骤)
    // 这样相同花色的牌会聚在一起，且内部有序
    sort(cards, cards + n);

    int max_keep = 0;

    // 2. 线性扫描，按花色分组处理
    for (int i = 0; i < n; ) {
        int j = i;
        
        // 找到当前花色的右边界 j (使得 cards[i...j-1] 是同一种花色)
        while (j < n && cards[j].suit == cards[i].suit) {
            j++;
        }
        
        // 此时 [i, j) 区间内全是同一种花色的牌
        
        // --- 提取数据 ---
        cur_nums.clear(); // 清空容器
        for (int k = i; k < j; k++) {
            cur_nums.push_back(cards[k].num);
        }
        
        // --- 处理这一组 ---
        max_keep = max(max_keep, solve());
        
        // --- 移动指针 ---
        i = j; //哪怕 j 越界也没关系，循环条件会终止
    }

    cout << n - max_keep << endl;

    return 0;
}

目录