題目描述

一個荒島上有若干人，島上只有一條路通往島嶼兩端的港口，大家需要逃往兩端的港口才可逃生。假定每個人移動的速度一樣，且只可選擇向左或 向右逃生。若兩個人相遇，則進(jìn)行決斗，戰(zhàn)斗力強(qiáng)的能夠活下來，并損失掉與對方相同的戰(zhàn)斗力;若戰(zhàn)斗力相同，則兩人同歸于盡。

輸入描述

給定一非0整數(shù)數(shù)組，元素個數(shù)不超過30000;正負(fù)表示逃生方向(正表示向右逃生，負(fù)表示向左逃生)，絕對值表示戰(zhàn)斗力，越左邊的數(shù)字表示離左邊港口越近，逃生方向相同的人永遠(yuǎn)不會發(fā)生決斗。

輸出描述

能夠逃生的人總數(shù),沒有人逃生輸出0，輸入異常時(shí)輸出-1。

示例1

輸入：
5 10 8 -8 -5

輸出：
2

說明：
第3個人和第4個人同歸于盡，第2個人殺死第5個人并剩余5戰(zhàn)斗力，第1個人沒有遇到敵人。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int p;
    vector<int> stk; // 用棧存儲向右側(cè)逃生中的人
    int cnt = 0; // 記錄從左側(cè)可以成功逃生的人數(shù)
    
    // 處理輸入數(shù)據(jù)
    while(cin >> p) {
        if (p > 0) { // 如果是正數(shù)，表示向右逃生，加入棧
            stk.push_back(p);
        }else{ // 如果遇到負(fù)數(shù)，表示向左逃生
            while (!stk.empty() && p < 0) {
                int last = stk.back(); // 棧頂元素
                stk.pop_back(); // 彈出棧頂元素

                p += last; // 進(jìn)行決斗，戰(zhàn)斗力相加
            }

            if (p < 0) { // 左逃生成功，計(jì)數(shù)
                cnt++;
            }else if(p > 0){ // 左逃生失敗
                stk.push_back(p);
            }
        }
    }

    // 輸出能逃生的人的數(shù)量
    cout << cnt + stk.size() << endl;
}

解題思路

1. 棧的使用：我們可以使用棧來模擬人們的逃生過程。每當(dāng)遇到一個向右逃生的人（正數(shù)），我們將其加入棧中；而當(dāng)遇到一個向左逃生的人（負(fù)數(shù)）時(shí)，可能會發(fā)生決斗：
   • 如果棧中有向右逃生的人，則進(jìn)行決斗，戰(zhàn)斗力較強(qiáng)的一方勝利。
   • 如果戰(zhàn)斗力相同，雙方都同歸于盡。
   • 如果沒有向右逃生的人，則該向左逃生的人直接逃生。
2. 棧的更新：
   • 當(dāng)一個人向左逃生時(shí)，首先檢查棧中是否有向右逃生的人，如果有，則比較戰(zhàn)斗力。
   • 如果向右逃生的人更強(qiáng)，棧中的人減少，向左逃生的人繼續(xù)與棧中的人決斗。
   • 如果向左逃生的人戰(zhàn)斗力足夠強(qiáng)，則可以殺死棧中的人，繼續(xù)決斗，直到?jīng)]有人阻擋他，或者他戰(zhàn)斗力為負(fù)（即同歸于盡）。
3. 最后的結(jié)果：棧中剩余的人表示逃生成功的人數(shù)。沒有遇到敵人的人直接逃生。每個人的戰(zhàn)斗力將會影響最終的逃生結(jié)果。
4. 輸入異常處理：如果輸入非法（如非整數(shù)輸入），則輸出 -1。

希望這個專欄能讓您熟練掌握算法, ?????? 立即訂閱。

整理題解不易， 如果有幫助到您，請給點(diǎn)個贊 ???? 和收藏 ?，讓更多的人看到。??????