[CSP-S 2024] 决斗

思路:刚开这道题就想到了二分，排序后找到每个元素比它第一个大的元素，由于 \(1 \leq n \leq 10^5\) ,直接暴力查找的话复杂度接近 \(O(n^2)\)，会超时，所以用二分。感觉思路并不复杂，代码+调试15分钟搞定，可惜今年s组没过。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, x;
struct bj {
	int num;
	bool flag, gjf;
};
vector<bj> v;
int bs(int k) {
	int r = n - 1, l = 0, res = -1;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (v[mid].num > k && v[mid].flag == true && v[mid].gjf == true) {
			res = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
	return res;
}
bool cmp(bj a, bj b) {
	return a.num < b.num;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back({x, true, true});
	}
	sort(v.begin(), v.end(), cmp);

	for (int i = 0; i < n - 1; i++) {
		int re = bs(v[i].num);
		if (re == -1) continue;
		else {
			v[i].flag = false;
			v[re].gjf = false;
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++)
		if (v[i].flag == true) ans++;
	cout << ans;
	return 0;
}