链接:

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;

}

巴特西

Codeforces Round #591 (Div. 2, based on Technocup 2020 Elimination Round 1) D. Sequence Sorting

链接:

题意:

思路:

代码:

最新文章

热门文章