C# · 12月 20, 2021

Codeforces Round #527 (Div. 3) D2. Great Vova Wall (Version 2) (栈)

题意:有n个列,然后输入n个数ai表示每个列当前的砖的个数,然后只有有1*2的砖,问最后能不能铺满n*max(ai)

思路:由于只能用1*2的砖,所以只有两块砖的高度相同时才可以消去,还有就是像这样的1221不满足题意,因为两边的相同的高度没法合在一起,像这样的2112这种才满足,最后可以有一列高度为h的墙,不过h要满足h >= max( h ) 才可以,用栈模拟过程。

#include

using namespace std;

#define read(x) scanf(“%d”,&x)

int main()

{

int n,h; read(n); int mx = -1;

stack sta;

for(int i = 0; i < n; i++)

{

read(h); mx = max(mx,h);

if(!sta.empty())

{

if(sta.top() < h) return puts("NO"),0;

if(sta.top() == h) sta.pop();

else sta.push(h);

}

else sta.push(h);

}

if(sta.size() > 1) puts(“NO”);

else if(sta.size() == 1 && sta.top() < mx) puts("NO");

else puts(“YES”);

}