這題要求判斷一組正負整數序列是否構成合法的「廣義套娃」結構。正整數代表開始一個尺寸為該值的娃娃,對應的負整數代表結束,且必須嚴格遵守「外層尺寸大於內層、同層之間不能相互重疊」的規則。輸入一行即一組測資,合法輸出 :-) Matrioshka!,否則輸出 :-( Try again.。
這是典型的括號配對問題,只是多了「尺寸必須遞減」的語意。做法是用一個堆疊保存尚未閉合的娃娃,每讀到一個數字就依情況處理:
#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(...)) 而非固定次數。