题解 [email protected]洛谷 【同花顺】

本题是一个有趣(?)的思维题,题意:要替换尽量少的牌,使得整套牌成为一个同花顺。


思路:容易想到,我们保留现有的最长的一条同花顺,将剩余的牌替换掉即可。

具体做法:

  • 读入数据先按照花色、数字进行排序和去重。
  • 枚举每一个点作为同花顺的右端点。
  • 找到左侧可以连成同花顺的第一张牌,计算同花顺长度,更新最长的长度。
  • 计算剩余的牌的数量,输出即可。

代码:

//By: [email protected]_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;
}