题解 P2652 【同花顺】
rui_er
2020-09-01 18:47:54
本题是一个有趣（？）的思维题，题意：要替换尽量少的牌，使得整套牌成为一个同花顺。
---
思路：容易想到，我们保留现有的最长的一条同花顺，将剩余的牌替换掉即可。
具体做法：
- 读入数据先按照花色、数字进行排序和去重。
- 枚举每一个点作为同花顺的右端点。
- 找到左侧可以连成同花顺的第一张牌，计算同花顺长度，更新最长的长度。
- 计算剩余的牌的数量，输出即可。
---
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, diff, ans;
struct Node {
int col, val;
bool operator < (const Node &a) const {
if(this->col != a.col) return this->col < a.col;
return this->val < a.val;
}
bool operator == (const Node &a) const {return (this->col == a.col) && (this->val == a.val);}
bool operator != (const Node &a) const {return !(*this == a);}
Node() {}
Node(int a, int b) : col(a), val(b) {}
~Node() {}
}a[N], b[N];
int col[N], val[N];
void discretization() {
sort(a+1, a+1+n);
b[++diff] = a[1];
for(int i=2;i<=n;i++) {
if(a[i] != a[i-1]) b[++diff] = a[i];
}
for(int i=1;i<=diff;i++) {
col[i] = b[i].col;
val[i] = b[i].val;
}
}
int main() {
scanf("%d", &n);
for(int i=1;i<=n;i++) scanf("%d%d", &a[i].col, &a[i].val);
discretization();
for(int i=2;i<=diff;i++) {
int uPos = lower_bound(val+(lower_bound(col+1, col+1+i, col[i])-col), val+i, val[i]-n+1) - val;
ans = max(ans, i-uPos+1);
}
printf("%d\n", n-ans);
return 0;
}
```