CF1919C 题解

yyrwlj · 2024-01-07 13:25:38 · 题解

题目传送门

题意简述

把一个序列分成两个子序列，使两个子序列中前一个数小于后一个数的情况最少，求出这个最小值。

思路

可以想象成有两个栈，要加入一个新的数。

若两个栈的栈顶元素全部小于当前数，那最终答案就只能加一，然后将当前数放到栈顶元素更小的那个栈。

若只有一个栈的栈顶元素大于等于当前数，那就把数放到那个栈里。

若两个栈的栈顶元素都大于等于当前数，那肯定要放到栈顶元素更小的那个栈里。

证明为什么要放到栈顶元素更小的那个栈

设 s1 是栈顶元素更小的栈的栈顶，s2 是栈顶元素更大的栈的栈顶，当前数为 a，下一个数为 b。

按照上面第三种情况，有 a \le s1 \le s2。

若 s1 < b \le s2，那么只有放到 s2 的后面才能使最终答案不加一。若当初 a 替换了 s2，有 a \le s1 < b，无论放到哪个栈都会使最终答案加一。

Code

#include <iostream>
using namespace std;
const int N = 200005;
int a[N];
void work()
{
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    int s1 = a[1], s2 = 2e9, ans = 0;
    for (int i=2;i<=n;i++)
    {
        if (s1 > s2)
        {
            if (a[i] <= s2)
                s2 = a[i];
            else if (a[i] <= s1)
                s1 = a[i];
            else
            {
                ans ++;
                s2 = a[i];
            }
        }
        else
        {
            if (a[i] <= s1)
                s1 = a[i];
            else if (a[i] <= s2)
                s2 = a[i];
            else
            {
                ans ++;
                s1 = a[i];
            }
        }
    }
    printf("%d\n", ans);
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        work();
    return 0;
}