一本通3.1棧黃色線：2020.3.9
熟悉的圖又回來了，其實(shí)這一次就一道題，還特簡單的一道
1357：車廂調(diào)度·
因?yàn)檫@次就一道題春瞬，我代碼就寫得細(xì)一點(diǎn)凳寺，前面的代碼解釋太少了鸭津，我把思路也寫寫
思路一：
模擬算法，因?yàn)閍[i]出棧前肠缨，若他在B軌上逆趋，則1~a[i]-1這些數(shù)都得在棧中或出棧，所以我就叫之前的全進(jìn)棧晒奕，至C中;而a[i]若在棧中闻书，壓在前面的必須出去，“放空”通道脑慧，讓a[i]出棧魄眉。詳見代碼解釋。
#include <bits/stdc++.h>
using namespace std;
int a[1050],n,nown=1;
//nown是當(dāng)前從B軌入棧的序號(hào)闷袒，當(dāng)前進(jìn)入到第幾個(gè)了
//因?yàn)槲沂怯行蜻M(jìn)棧坑律，那就是最后進(jìn)棧的編號(hào)
stack<int> s;//棧
//stack（棧）可用數(shù)組代替，但我更喜歡用stack囊骤，操作起來方便晃择，也好用
int main()
{
? cin>>n;
? for(int i=1; i<=n; i++) cin>>a[i];//輸入
? for(int i=1; i<=n; i++)
? {
? ? while(nown<=a[i])//若在B軌上
? ? ? s.push(nown++);//把前面的壓入
? ? if(s.top()==a[i]) s.pop();//如果棧頂是當(dāng)前的要出棧車廂號(hào)，那么就出棧也物。
? ? else//不然就說明無法達(dá)到目標(biāo)宫屠，輸出“NO”
? ? {
? ? ? cout<<"NO\n";//一定要大寫哦
? ? ? return 0;
? ? }
? }
? cout<<"YES\n";//大寫哦
? return 0;
}
思路二：按題目說的方法
//
? ? ?從第一個(gè)數(shù)字開始掃描，a[i]表示當(dāng)前出棧的數(shù)字滑蚯，如果有比a[i]大的數(shù)字還在棧中浪蹂，那么就產(chǎn)生矛盾，輸出“NO”告材；否則坤次，標(biāo)記當(dāng)前數(shù)字a[i]為棧后狀態(tài)，那么[1, a[i]-1]這些數(shù)字如果還沒出棧创葡，標(biāo)記為棧中狀態(tài)浙踢。具體我們可以用0表示為確定狀態(tài)绢慢，1表示棧中狀態(tài)灿渴，2表示棧后狀態(tài)。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ——ybt一本通（??鼻涕）官方網(wǎng)站
//
那就簡單了胰舆，代碼嘛骚露，直接上
#include <bits/stdc++.h>
using namespace std;
int sta[1050],a[1050],n,top,nown[1050];
int main()
{
? cin>>n;
? for(int i=1; i<=n; i++)
? {
? ? cin>>a[i];
? ? if(nown[a[i]]==1)//在棧中
? ? ? if(sta[top--]==a[i])//最上面
? ? ? ? nown[a[i]]=2;//推到棧后
? ? ? else
? ? ? {
? ? ? ? cout<<"NO"<<endl;
? ? ? ? return 0;//輸出不可能
? ? ? }
? ? for(int j=1; j<a[i]; j++)//前面未入棧的
? ? {
? ? ? if(nown[j]==0)
? ? ? {
? ? ? ? nown[j]=1;
? ? ? ? sta[++top]=j;
? ? ? }//入棧
? ? }
? ? nown[a[i]]=2;//a[i]出棧（棧后）
? }
? cout<<"YES"<<endl;
? return 0;
}
這種方法有點(diǎn)煩，不過也是一種好的方法缚窿，能過就行棘幸。
? ? ? ? 總結(jié)一下，兩種方法倦零，各有各的好處误续，當(dāng)然吨悍，網(wǎng)上給的代碼全是第一種，其實(shí)第二種也不錯(cuò)啦蹋嵌，看個(gè)人選擇育瓜。有提示，順著它最好栽烂，但用自己的方法躏仇，也不是說差。有興趣的腺办，可以像我一樣焰手，兩種思路都碼，可以練練手怀喉。
