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,那么横过来就一定无法变为aiif(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;
}