cf Hello 2024 C. Grouping Increases
作者:
さのpool
,
2024-01-07 09:54:15
,
所有人可见
,
阅读 99
贪心分类讨论
最多可以分为两组那怎么分呢?
1,如果第一次出现了递增的情况,那就可以将其分为两个序列
2.我们每次考虑将这个元素接到一个序列的后面,使出现递增的可能性最小
具体为:
- 1.如果这个元素比两个序列的末尾都要大则接到末尾更小的那一个上
- 2.如果这个元素比两个序列的末尾都要小则接到末尾更小的序列后面
- 3,如果一个序列末尾比这个元素大另一个比这个元素小则肯定接在比这个元素大的末尾
(ps:很可惜昨天acwing第二题没做出来,但是cf昨天上了点小分,底下两周是考试周,我还要准备另一个更重要的考试应该会减少写代码的时间)
#include <iostream>
#include <cstring>
#include <algorithm>
#include<cmath>
using namespace std;
void solve()
{
int n;
scanf("%d",&n);
int x1 =1e9,x2 = 1e9;
int ans = 0;
for(int i = 0;i<n;i++)
{
int a;
scanf("%d",&a);
if(i == 0)
{
x1 = a;
continue;
}
if(a<=x1&&a<=x2)
{
if(x1>x2) x2 = a;
else x1 = a;
}
else if(a<=x1&&a>x2)
{
x1 = a;
}
else if(a>x1&&a<=x2)
{
x2 = a;
}
else if(a>x1&&a>x2)
{
if(x1<x2) x1 = a;
else x2 = a;
ans ++;
}
}
printf("%d\n",ans);
}
int main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}