您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發綜合

UVa 11111 Generalized Matrioshkas:用堆疊式配對檢驗套娃結構

編輯:iOS 開發綜合

這題要求判斷一組正負整數序列是否構成合法的「廣義套娃」結構。正整數代表開始一個尺寸為該值的娃娃,對應的負整數代表結束,且必須嚴格遵守「外層尺寸大於內層、同層之間不能相互重疊」的規則。輸入一行即一組測資,合法輸出 :-) Matrioshka!,否則輸出 :-( Try again.。

解題思路

這是典型的括號配對問題,只是多了「尺寸必須遞減」的語意。做法是用一個堆疊保存尚未閉合的娃娃,每讀到一個數字就依情況處理:

  • 遇到正整數,代表進入新的一層,直接壓入堆疊。
  • 遇到負整數,檢查堆疊頂是否為同尺寸的對應正數。若是,則彈出並記錄這一層內部已收好的娃娃總尺寸;同時必須驗證內部累積尺寸嚴格小於外層尺寸,否則代表內容量超出,結構不合法。
  • 若堆疊已空卻還遇到負數,或到輸入結束時堆疊仍有殘留、或最外層並未形成單一完整的套娃,都判為不合法。

C++ 實作

#include <iostream>
#include <vector>
#include <utility>
#include <sstream>
#include <string>
#include <cmath>
#include <limits>
using namespace std;

int main() {
    const int IntMin = numeric_limits<int>::min();
    string line;

    while (getline(cin, line)) {
        istringstream input(line);
        int x;
        vector<int> vi;
        while (input >> x) vi.push_back(x);

        int i = 0, size = vi.size();
        // pair.first 為尺寸,pair.second 為該層內已累積的內容量
        // 以 IntMin 作為「已完成一層」的標記
        vector<pair<int,int> > vp;
        vp.push_back(make_pair(vi[0], 0));

        for (i = 1; i < size; ++i) {
            int j = vp.size() - 1;
            int inner = 0;

            // 向前累計所有已閉合層的內容量
            while (j >= 0 && vp[j].first == IntMin) {
                inner += fabs((double)vp[j].second);
                --j;
            }
            if (j < 0) break;

            if (vi[i] == -vp[j].first) {
                // 內容量必須嚴格小於外層尺寸
                if (inner >= fabs((double)vi[i])) break;
                vp.erase(vp.begin() + j, vp.end());
                vp.push_back(make_pair(IntMin, vi[i]));
            } else {
                vp.push_back(make_pair(vi[i], 0));
            }
        }

        // 全部讀完、堆疊只剩一層且該層已閉合,才算合法
        if ((i >= size) && (vp.size() == 1) && vp[0].first == IntMin)
            cout << ":-) Matrioshka!" << endl;
        else
            cout << ":-( Try again." << endl;
    }
    return 0;
}

幾個容易失分的細節

  • 合法性判斷有三個條件必須同時成立:輸入完整讀完、堆疊只剩一個元素、且該元素是閉合標記。少檢查任何一項都會出現誤判。
  • 「內容量必須嚴格小於外層尺寸」用 >= 判斷後 break,等號要放在錯誤那側。
  • 以整行讀入再用 istringstream 切分,比直接串流讀取更好控制單組測資的邊界。
  • 題目未明說測資行數,因此外層用 while (getline(...)) 而非固定次數。
  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved