CF1863B Split Sort 题解

Links

洛谷

Codeforces

Description

给定一个 \(1 \sim n\) 的排列 \(q\)，你可以多次进行以下操作：

• 新建一个初始为空的序列 \(q\)；
• 选择一个整数 \(x\)（\(2 \leq x \leq n\)）；
• 按照在 \(p\) 中出现的顺序将所有小于 \(x\) 的数添加到序列 \(q\) 末尾。
• 按照在 \(p\) 中出现的顺序将所有大于等于 \(x\) 的数添加到序列 \(q\) 末尾。
• 用序列 \(q\) 替代排列 \(p\)。

你需要找到使 \(\forall i \in [1,n]\)，\(p_{i} = i\) 的最小操作次数。

本题有多组测试数据，\(1 \leq T \leq 10^{3}\)，\(1 \leq n,\sum n \leq 10^{5}\)。

Solution

比较简单的题，一个很显然的结论，设 \(pos_{i}\) 是 \(i\) 在原序列出现的的位置，如果 \(pos_{i} > pos_{i - 1}\) 那么我们必须选择 \(i\) 进行一次操作。只有这样能改变 \(i\) 与 \(i - 1\) 的相对顺序，而选择其他位置不会改变其相对顺序。因此我们有唯一的操作方案，对于每个 \(pos_{i - 1} > pos_{i}\) 的 \(i\) 操作一次。

Codes

#include <bits/stdc++.h>
using namespace std;
#define int long long
void read(int &p)
{
    p = 0;
    int k = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
        {
            k = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        p = p * 10 + c - '0';
        c = getchar();
    }
    p *= k;
    return;
}
void write_(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
    {
        write_(x / 10);
    }
    putchar(x % 10 + '0');
}
void writesp(int x)
{
    write_(x);
    putchar(' ');
}
void writeln(int x)
{
    write_(x);
    putchar('\n');
}
int T,n,ans;
int nums[100001],pos[100001];
void solution()
{
    ans = 0;
    read(n);
    for(int i = 1;i <= n;i++)
    {
        read(nums[i]);
        pos[nums[i]] = i;
    }
    for(int i = 1;i < n;i++)
    {
        if(pos[i] > pos[i + 1])
        {
            ++ans;
        }
    }
    writeln(ans);
    return ;
}
signed main()
{
   // freopen("1.in","r",stdin);
    read(T);
    while(T--)
    {
        solution();
    }
    return 0;
}