目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

B - Uniqueness

---

二、解题报告

1、思路分析

观察单调性：对于合法的删除区间 [l, r] r 右移，l 要么右移要么不动，一定不左移

我们考虑二分

二分删除区间的长度 x

我们 枚举r，维护l，哈希表mp 存储 [l, r] 外元素出现次数

如果 mp 的 size 等于 n - （r - l + 1），那么次数合法，我们尝试右收缩左边界

只要收缩过程中 n - (r - l + 1) <= m，我们就返回true

2、复杂度

时间复杂度： O(NlogN)空间复杂度：O(N)

3、代码详解

 ​

#include <bits/stdc++.h>// #define DEBUGusing u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;struct custom_hash {static u64 splitmix64(u64 x) {x ^= x << 13;x ^= x >> 7;x ^= x << 17;return x; }size_t operator () (u64 x) const {static const u64 FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); // 时间戳return splitmix64(x + FIXED_RANDOM);}
};using safemap = std::unordered_map<u64, u64, custom_hash>;void solve() {int n;std::cin >> n;std::vector<int> a(n);safemap st;for (int i = 0; i < n; ++ i) {std::cin >> a[i];++ st[a[i]];}if (st.size() == n) {std::cout << "0\n";return;}auto check = [&](int m) -> bool{safemap mp = st;for (int r = 0, l = 0; r < n; ++ r) {if (!-- mp[a[r]])mp.erase(a[r]);while (mp.size() == n - (r - l + 1)) {if (r - l + 1 <= m) return true;if (!-- mp[a[l]])mp.erase(a[l]);++ l;}}return false;};int lo = 0, hi = n;while (lo < hi) {int x = (lo + hi) / 2;if (check(x)) hi = x;else lo = x + 1;}std::cout << hi << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);#ifdef DEBUGint cur = clock();freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint t = 1;// std::cin >> t;while (t--) {solve();}
#ifdef DEBUGstd::cerr << "run-time: " << clock() - cur << '\n';
#endifreturn 0;
}