C. Sort Zero

题目描述
思路分析:
记住他是要保证这个数列是不降的,也就是说如果某一个位置上的数变成了0,那么这个数前面的部分一定全都是0了,我们用map数组得到每一个数出现的最晚的位置,先从后向前遍历一遍,找出从哪开始出现了递减,然后标记下来结束即可,看看前面的每一个数都要用st标记是不是要归零,然后保证他们的这个数的最后的位置前面全是0,记住了st数组要用st[a[i]]=0来初始化,别用memset会超时

#include
#include
#include
#include
#include
using namespace std;
int a[100010], st[1000010];
int ans,t;
int main()
{
	cin >> t;
	while (t--){
		int n, temp = -1;
		cin >> n;
		ans = 0;
		map<int, int>mp;//记录最后出现的位置
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			st[a[i]] = 0;
			mp[a[i]] = max(mp[a[i]], i);//不断往后看
		}
		if (n == 1) {
			cout << 0 <<endl; continue;
		}
		for (int i = n; i >= 2; i--)
		{
			if (a[i] < a[i - 1]){
				temp = i-1; //记录0应该出现的最后的位置
				break;
			}
		}
		if (temp == -1) {
			cout << 0 << endl; continue;
		}
		int maxx = -1, ans = 0;
		for (int i = 1; i <= temp; i++)
		{
			maxx = max(maxx, mp[a[i]]);
		}
		for (int i = 1; i <= maxx; i++)//往前都要变成零 
		{
			if (a[i] && st[a[i]] == 0)
			{
				st[a[i]] = 1;//标记
				ans++;//答案
			}
		}
		cout << ans << endl;
	}
	return 0;
}