链接:
https://codeforces.com/contest/1241/problem/D
题意:
You are given a sequence a1,a2,…,an, consisting of integers.
You can apply the following operation to this sequence: choose some integer x and move all elements equal to x either to the beginning, or to the end of a. Note that you have to move all these elements in one direction in one operation.
For example, if a=[2,1,3,1,1,3,2], you can get the following sequences in one operation (for convenience, denote elements equal to x as x-elements):
[1,1,1,2,3,3,2] if you move all 1-elements to the beginning;
[2,3,3,2,1,1,1] if you move all 1-elements to the end;
[2,2,1,3,1,1,3] if you move all 2-elements to the beginning;
[1,3,1,1,3,2,2] if you move all 2-elements to the end;
[3,3,2,1,1,1,2] if you move all 3-elements to the beginning;
[2,1,1,1,2,3,3] if you move all 3-elements to the end;
You have to determine the minimum number of such operations so that the sequence a becomes sorted in non-descending order. Non-descending order means that for all i from 2 to n, the condition ai?1≤ai is satisfied.
Note that you have to answer q independent queries.
思路:
记录每个值的左端点和右端点,
然后找出满足范围不相交的最长的连续值.
比赛想了半天硬是没想到能记录两个点..
代码:
#include <bits/stdc++.h> using namespace std; const int MAXN = 3e5+10; set<int> St; int l[MAXN], r[MAXN]; int n; int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while(t--) { St.clear(); int v; cin >> n; for (int i = 1;i <= n;i++) l[i] = n, r[i] = 1; for (int i = 1;i <= n;i++) { cin >> v; l[v] = min(i, l[v]); r[v] = max(i, r[v]); St.insert(v); } int cnt = 0, rp = -1, ans = 0; for (auto x: St) { if (l[x] > rp) cnt++; else cnt = 1; rp = r[x]; ans = max(cnt, ans); } cout << St.size()-ans << endl; } return 0; }