uva 11111 - Generalized Matrioshkas

点击打开链接

题目意思： 这一题题目真心不好看懂，所以呢，我就大概描述一下，题目是说有一个娃娃大小为k可以拆成 -k 和 k ，然后娃娃里面可以嵌套物品，但是规定内层娃娃的大小是不能超过 外层的大小的， 现在给定一个娃娃的尺寸大小序列，左边的是负数，问我们这个序列是不是一个物品所拆开的，相应输出题目所要求的内容。

解题思路： 1：这一题和括号匹配非常像，只是多了一个判断内层的大小和外层的关系。我们可以建立一个Toy结构体，存储当前娃娃的大小以及当前剩余的空间，那么我们用一个栈来存储结构体，用k数组存储读入的娃娃的尺寸。
2：那么我们分序一下这个过程：如果当前的读入的k[i]是负数说明这时候是嵌套在外层上，那么我们就判断当前所剩下的空间是否大于这个娃娃的尺寸，如果不是这接退出，否则入栈；如果k[i]是正数，判断能否和栈顶的元素的val相加为0，如果是退栈，更新剩余的空间（只要把栈顶处剩余的空间减去k[i]即可）；如果判断此时栈为空但是娃娃没有取完也直接退出。最后要满足则是栈为空，说明完全匹配
3：不满足的情况：1 娃娃的个数为奇数个 2 最后栈不为空

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 1000010;

int cnt, ans;
int k[MAXN];
//娃娃结构体
struct Toy {
    int val;
    int rest;
};
stack<Toy>s;

//判断是否满足条件
void solve() {
    while (!s.empty())//每一次对栈清空
        s.pop();
    //先把第一个给入栈
    Toy temp;
    temp.val = k[0];
    temp.rest = abs(k[0]);
    s.push(temp);
    for (int i = 1; i < cnt; i++) {
        if (s.empty())//如果栈为空
            return;
        if (k[i] < 0) {//如果为负数
            if (abs(k[i]) < s.top().rest) {//剩余空间大于这个k[i]
                Toy temp;
                temp.val = k[i];
                temp.rest = abs(k[i]);
                s.push(temp);//入栈
            } 
            else
                return;
        } 
        if (k[i] > 0) {//大于0时候就判断栈顶是否和它匹配
            if (k[i] + s.top().val == 0) {//相加为0时候
                if(i != cnt-1){//还没到最后一个元素，删除栈顶元素
                    s.pop();
                    s.top().rest -= k[i];
                }
                else
                    s.pop();//到了最后一个时候只要pop即可
            } 
            else
                return;
        }
    }
    if(s.empty())//如果栈为空那么就另ans为1
        ans = 1;
}

//主函数
int main() {
    int x;
    char c;
    //注意输入的格式
    while (~scanf("%d%c", &x, &c)) {
        k[0] = x;
        cnt = 1;
        ans = 0;
        if (c != '\n') {
            while (scanf("%d%c", &k[cnt++], &c)) {
                if (c == '\n')
                    break;
            }
        }
        if (cnt % 2 == 0)//如果是偶数个才进行solve();
            solve();
        if (ans)
            printf(":-) Matrioshka!\n");
        if (!ans)
            printf(":-( Try again.\n");
    }
    return 0;
}