---
title: Codeforce 319 B. Psychos in a Line 解析(思維、單調棧)
description: "Codeforce 319 B. Psychos in a Line 解析(思維、單調棧)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 319 B. Psychos in a Line 解析(思維、單調棧)">
<!-- toc -->

# Codeforce 319 B. Psychos in a Line 解析(思維、單調棧)
今天我們來看看CF319B
[題目連結](https://codeforces.com/problemset/problem/319/B)

> **題目**
給一個數列，如果相鄰兩數，左邊大於右邊，那麼就可以殺死右邊的數字(被殺死的數字在當前一輪也可以殺右邊的數字)
求幾輪以後就沒有數字會自相殘殺了?

### 前言
第一眼看到就感覺會和單調棧有關，但是實在經驗不足，最後思緒被拉跑到找遞增和遞減數列了...

### 想法
我們都知道，單調棧最一開始就是拿來找一個元素往左或往右的，第一個比元素本身大或小的元素。
但這題還需要我們利用單調棧運行時的過程。
首先我們從數列左邊開始處理(跑單調棧找往左看第一個比自身大的)，並且將第$i$個元素在第幾輪會被殺掉儲存為$pre[i]$，接著注意到這件事(令第$i$元素往左看第一個大於的元素的index為$j$):$pre[i]=\min\{i-j,[j+1,i]區段中最大的pre[.]+1\}$，其中$i-j$代表最慢的情況就是由左邊第一大的元素慢慢殺過來，而後者代表$[j+1,i]$這一段都被殺完以後，下一個就是自己被殺。
而重點就在於尋找$[j+1,i]區段中最大的pre[.]$可以在stack pop的同時計算。其原因是因為:假設目前$[j,i]$區段已經有一些元素被pop走了，剩下等著還沒pop的元素當然有可能是最大值，要計入考慮，而這些剩下的元素都已經計算過$pre[i']=\min\{i'-j',[j'+1,i']區段中最大的pre[.]+1\}$，又，$i'-j'\ge[j'+1,i']區段中最大的pre[.]+1$。所以只要計算還在stack中的最大值，就等於整個$[j+1,i]$區間的最大值了。
最後只要輸出$pre[.]$中的最大值就好。

### 程式碼:

const int _n=1e5+10;
int t,n,a[_n];
int pre[_n];
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n;rep(i,0,n)cin>>a[i];
  stack<int> s;rep(i,0,n){
    while(!s.empty() and a[s.top()]<a[i]){
      pre[i]=max(pre[i],pre[s.top()]);s.pop();
    }
    pre[i]=min(s.empty()?0:i-s.top(),pre[i]+1);
    s.push(i);
  }int maxx=-1e9;rep(i,0,n)maxx=max(maxx,pre[i]);
  cout<<maxx<<'\n';
  return 0;
}

標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/319/submission/90472213)