20. 填坑Ⅱ
成績 10 開啟時間 2020年09月17日 星期四 12:00 折扣 0.8 折扣時間 2020年09月24日 星期四 12:00 允許遲交 否 關閉時間 2020年10月10日 星期六 23:00 Description
emmm，還是北湖深坑，不用驚喜，不用意外，
我們繼續用石頭填！北湖的地面依舊是一維的，每一塊寬度都為1，高度是非負整數，用一個陣列來表示，
還是提供不限量的1x2規格的石頭，但是這一次是 Dark來填坑，他有很強烈的強迫癥，所有的石頭只能水平擺放（寬為2，高為1），問這樣是否可以將北湖填平，（所有地面到達同一高度即為填平）
Input
樣例有多組輸入至檔案末尾；
每組用例占兩行；
第一行輸入1個整數 n表示北湖地面總寬度；
第二行輸入 n個整數,用空格間隔，表示地面高度，
Output
若能填平則輸出“YES”，否則輸出“NO”，
測驗輸入 期待的輸出 時間限制 記憶體限制 額外行程 測驗用例 1
- 5?
- 2 1 1 2 5?
- 3?
- 4 5 3?
- 3?
- 1 2 3?
- YES?
- NO?
- NO?
1秒 64M 0
emmmm我總覺得個填坑Ⅱ和Ⅰ反了，但是怎么今年依舊還是這個順序....相信看懂Ⅰ的朋友這個Ⅱ真的小菜一碟！
第一題的傳送門，請看懂第一題再來看第二題：填坑Ⅱ | 簡單的資料結構
既然不可以以1為底2為高去填，那么與第一題的思路差別就是：
- 最后的結果判定為yes的條件：堆疊最后為空 或 堆疊內剩余的唯一元素必須是最高點（好好想想這是為啥）
- 我們不可以對坑進行預處理（將他們盡可能填到最高處），我們直接討論之后的情況，情況變得非常簡單：入堆疊的不是01，而是它們本身的高度！
依次討論每一個初始高度，如果相鄰的同高且兩側都比它們倆低，那么可以消去忽略不計，如果最后序列里有超過一個元素或剩余的唯一元素不是最高點，則輸出NO！如果在討論的程序中，堆疊頂元素比堆疊內高，那我們可以不必繼續討論....
你們可以多畫一些測驗用例來理解如上思路，雞翅能力有限(兩點了，該睡會了)說不太明白，上面都是精華，剩下的就交給大家了~
附上完整ac代碼：
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
long long int a[200010] = {0};
stack<int> stk; //定義一個堆疊
int main() {
long long int n, x = 2e18;
//當存在輸入的時候
while (scanf("%lld", &n) != EOF) {
memset(a, 0, sizeof(a[0])); //將陣列初始化為0
while (!stk.empty()) //清空堆疊
stk.pop();
long long maxHeight = 0;
for (long long i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
//記下最高值
if (a[i] > maxHeight)
maxHeight = a[i];
}
for (long long height : a) {
if (!stk.empty() && height == stk.top()) //堆疊非空且可以對應時
stk.pop();
else { //不可以消去
if (!stk.empty() && stk.top() < height) //如果比前一個高
break;
else
stk.push(height);
}
}
long long remainCount = stk.size();
if (!remainCount)
printf("YES\n");
else if (remainCount == 1 && stk.top() == maxHeight)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
End
歡迎關注個人公眾號“雞翅編程”，這里是認真且乖巧的碼農一枚，旨在用心寫好每一篇文章，平常會把筆記匯總成推送更新~
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/89427.html
標籤：其他
上一篇：云棲大會限時搶答賽
下一篇：什么是 DMP？