Problem - C - Codeforces
题目大意 :
给你一个 序列,和一个操作:选择一个x,并且让所有等于x的数为0
问让这个序列变成非递减序列的最小操作次数是多少
思路:
预处理:定义一个map ,q用来存每个数出现的最长到达的长度,p用来存这个数是否出现
首先找递减的最长的点L,然后这个点要变成0(不然不能满足非递增),因为这个点变成0了, 所以之前的都要变成0,然后从第一个数到第L之间的数都要变成0,那么这些数出现的对应的所有位置也要变成0,那么再用q找0的最长的长度就是要变成0的区域,之后再用p找需要进行几次操作就好。
/**
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/
#include<cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include<vector>
#include<queue>
#include<map>
#define ll long long
using namespace std;
const int N=1000000+100;
int n ,m,h;
ll s[N];
map<int,int>q,p;
int main()
{
int t;
cin>>t;
while(t--)
{
q.clear();
p.clear();
cin>>n;
for(int i =1;i<=n;i++){
cin>>s[i];
p[s[i]]++;
q[s[i]]=max(q[s[i]],i);
}
int j=0;
for(int i =1;i<=n;i++)//非递减序列
{
if(s[i]>s[i+1]&&i+1<=n)
j=i;
}
int res=j;
for(int i =1;i<=j;i++)
res=max(q[s[i]],res);
int ans=0;
for(int i =1;i<=res;i++)
{
if(p[s[i]])
ans++;
p[s[i]]=0;
}
cout<<ans<<endl;
}
return 0;
}