dinnerhunt

You are given a sequence 𝑎1,𝑎2,…,𝑎𝑛, consisting of integers.

You can apply the following operation to this sequence: choose some integer 𝑥 and move all elements equal to 𝑥 either to the beginning, or to the end of 𝑎. Note that you have to move all these elements in one direction in one operation.

For example, if 𝑎=[2,1,3,1,1,3,2], you can get the following sequences in one operation (for convenience, denote elements equal to 𝑥 as 𝑥-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 𝑎 becomes sorted in non-descending order. Non-descending order means that for all 𝑖 from 2 to 𝑛, the condition 𝑎𝑖−1≤𝑎𝑖 is satisfied.

Note that you have to answer 𝑞 independent queries.

链接🔗

「CodeForces 1241D」Sequence Sorting

题解

我们把每个数字分成最左点和最右点，那么该数字边成为了一个区间「L，R」
连续上升区间就是连续并且相邻两个数字的区间没有相交
我们的目标则是将整个区间数组变成连续上升的
答案为N - 未移动前的最长连续上升区间长度

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <map>
#include <iostream>
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int maxd = 2e5+10;
typedef long long ll;
int main()
{
//    freopen("a.in","r",stdin);
//    freopen("k.out","w",stdout);
    int t;scanf("%d",&t);
    while(t--)
    {
        int n;scanf("%d",&n);
 
        vector<int> a(n),b(n);
        map<int,int> mp;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            b[i] = a[i];
        }
        sort(all(b));
        b.erase(unique(all(b)),b.end());
        int m =b.size();
        vector<int> l(m),r(m),dp(m);
 
        for(int i=0;i<m;i++) mp[b[i]] = i;
        for(int i=0;i<n;i++) r[mp[a[i]]] = i;
        for(int i=n-1;i>=0;i--) l[mp[a[i]]] = i;
        //for(int i=0;i<m;i++) printf("%d %d\n",l[i],r[i]);
        for(int i=0;i<m;i++) dp[i] = 1;
        int ans = 1;
        for(int i=1;i<m;i++)
        {
            if(r[i-1] < l[i]) dp[i] = dp[i-1] +1;
            ans = max(dp[i],ans);
        }
        printf("%d\n",m-ans);
 
    }
 
    return 0;
}