Codeforces Round 894 (Div. 3)-----＞C. Flower City Fence

题目总思路：

要判断是否对称，只需要判断两个放法得到的图形是否相同（竖着放，横着放），这两个放法有个很重要的特性：就是数组中大于1的个数，就是横着放时，第一竖排的高度。那么我们只需要比较两个放法得到的图形，高度是否全部一致。

方法一 :记忆性标记

1.思路：

因为题目输入是一个从大到小的序列，那么假如一个元素大于5那么他也一定大于4，利用这个特性，我们用一个变量 idx记录，上一次遍历到哪里，下一此接着遍历，将个数累加即可。

2.代码：

#include <iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;const int N=2e5+10;int h[N] ;
void Solved(){int n;cin>>n;for(int i=1;i<=n;i++) cin>>h[i];//cnt统计符合条件的元素数量int idx=1, cnt=0;bool flag=true;for(int i=n;i>=1;i--){while(idx<=n&&h[idx]>=i){idx++,cnt++;}if(cnt!=h[i]) {flag=false;break;}}if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;}int main()
{int t;cin>>t;while(t--) {Solved();}return 0;
}

二 ， 方法二 :

1.思路：可以利用差分思想，因为一个程度为 x的木块，他横着放能为这个图形的 [1,n]这个范围，每一个高度增加 1。

2.代码：

#include <iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;const int N=2e5+10;
typedef long long ll;
int h[N] ,temp[N];
void Solved(){memset(temp,0,sizeof temp);int n;cin>>n;for(int i=1;i<=n;i++) cin>>h[i];//注意特判，不然会数组越界。if(h[1]>n){cout<<"NO"<<endl;return;}//差分思想for(int i=1;i<=n;i++){temp[1]++;temp[h[i]+1]--;}//差分数组求前缀和for(int i=1;i<=n;i++) temp[i]+=temp[i-1];bool flag=true;for(int i=1;i<=n;i++){if(temp[i]!=h[i]){flag=false;break;}}if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;
}int main()
{int t;cin>>t;while(t--) {Solved();}return 0;
}

三，方法三·：二分找大于某个长度的元素数量。

代码：

#include <iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;const int N=2e5+10,M=1e9+10;
typedef long long ll;
int h[N] ,temp[N];
void Solved(){memset(temp,0,sizeof temp);int n;cin>>n;for(int i=1;i<=n;i++) cin>>h[i];bool flag=true;for(int i=n;i>=1;i--){int l=1,r=n;while(l<r){int mid=(l+r+1)>>1;if(h[mid]>=i) l=mid;else r=mid-1;}if(l!=h[i]){flag=false;break;}}if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;
}int main()
{int t;cin>>t;while(t--) {Solved();}return 0;
}