C、Flower City Fence

跳转原题点击此：该题地址

1、题目大意

  给你n块长度依次不递增的紧密连接在一起的垂直木板，将它们水平横过来，问其组成的全新n块木板的长度是否与原来的木板长度一致。
  注意：这里的长度是指：木板的高度。水平摆放后的木板是左对齐，所以其长度就是各个木板水平摆放后的连接高度。(语言容易表达不清晰，建议看原题的图)。

2、题目解析

  我们注意到，水平摆放后的木板高度就是每格的木板数量。我们得从后往前推，当前格的木板数量少了 则 木板高度也就少了。所以我们令\(a[i] = 木板长度\)，\(b[木板长度] = i\)就能得到水平摆放后的木板高度。
  但是如果存在连续的木板高度就会出现\(b[i]==0\) 的情况，解决方法为：因为原木板高度是非递增的，通过\(max(b[i], b[i+1]\)就能依次填补b数组中为0的情况（\(b[i] \ge b[i + 1]\)）。
  又因为水平摆放后的木板高度是每格的木板数量，当原输入的木板长度大于n时，水平摆放后就一定与原长度不一致。

3、具体代码

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5+10;

int T;
int n;
int a[N], b[N];

void solve()
{
	cin >> n;
	memset(b, 0, sizeof b);
	for(int i = 1; i <= n; i++)
		cin >> a[i];
		
	for(int i = 1; i <= n; i++)
	{
		// 如果ai大于n，那么横过来就一定无法变为ai
		if(a[i] > n)
		{
			cout << "NO\n";
			return;
		}
		// 因为是a[i] = 高度，而b数组则反过来b[高度] = i
		// 因为高度会重复，所以通过max(b[i], b[i + 1])来更新
		b[a[i]] = i;
	}
	
	// 倒着过来是因为由于题干是不递增地顺序，所以倒过来后，值越小的就越高
	for(int i = n; i > 0; i--)
	{
		b[i] = max(b[i], b[i + 1]);
		if(b[i] != a[i])
		{
			cout << "NO\n";
			return;
		}
	}
	cout << "YES\n";
}

int main()
{
	cin >> T;
	while (T--)
	{
		solve();
	}

	return 0;
}