TIOJ 1441 . 萬里長城

題目鏈接:https://tioj.ck.tp.edu.tw/problems/1441

這題寫了超久...卡在幾個情況沒想到,這次把他記錄下來
最一開始我寫出的code大概是如下這樣

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define AC ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

int main()

{

AC

ll n,t;

bool b=0;

cin>>n;

stack<ll,list<ll>> s;

cin>>t;

s.push(t);

while(--n)

{

cin>>t;

if(t<s.top()^b)

{

b^=1;

s.push(t);

}

}

cout<<s.size()+b<<'\n';

}

最一開始我用的版本還是沒有把stack修改為list當容器的,直接吃了一個MLE

上面的code還有一個很重要的問題

就是沒注意到XOR的運算優先順序和前後兩個石頭數字相等時應另外處理而不是讓他(t<s.top())=false

此外

應前後兩者的關係不會被其他石頭所影響,則空間可優化

用變數t表示 t=h[i-1]

再者,應取大時若沒取,則h[i+1]≥h[i]

同理可得取小時若沒取,則h[i+1]≤h[i]

所以每次循環結束都更新t=h[i]必為最優解

code如下

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define AC ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

int main()

{

AC

ll n,t=-1,r=0;

cin>>n;

bool b=1;

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

{

ll h;

cin>>h;

if((h<t)^b&&h!=t)

{

b^=1;

r++;

}

t=h;

}

cout<<r-b<<'\n';

}