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;
}
时间: 2024-12-24 20:56:01

uva 11111 - Generalized Matrioshkas的相关文章

UVa 11111 Generalized Matrioshkas:栈

11111 - Generalized Matrioshkas Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=2052 Vladimir worked for years making matrioshkas, those nesting dolls th

UVa 1111 Generalized Matrioshkas 数据结构专题

题目链接接: http://uva.onlinejudge.org/index.phpoption=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=2052 题目类型: 数据结构, 链表 题目大意: 这题的题意比较难懂,看了好几变才明白.  就是有一个可以嵌套娃娃的娃娃,然后嵌套在里面的娃娃又可以继续嵌套娃娃. 然后要求直接嵌套在里面(内一层)的娃娃的尺寸大小之和不能超过外面的. 例如,-3 -

UVa 11076 Add Again (组合数学)

11076 - Add Again Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php? option=com_onlinejudge&Itemid=8&category=467&page=show_problem&problem=20 17 Summation of sequence of integers is always a common problem in Computer Science

UVa 10602

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1543 类型:贪心 原题: Company Macrohard has released it's new version of editor Nottoobad, which can understand a few voice commands.

UVa 10392 Factoring Large Numbers:素因子分解

10392 - Factoring Large Numbers Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=100&page=show_problem&problem=1333 One of the central ideas behind much cryptography is that factoring

UVa 10182 Bee Maja:规律&amp;amp;O(1)算法

10182 - Bee Maja Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1123 Maja is a bee. She lives in a bee hive with thousands of other bees. This bee hive c

算法题之UVA 763

Fibinary Numbers The standard interpretation of the binary number 1010 is 8 + 2 = 10. An alternate way to view the sequence ``1010'' is to use Fibonacci numbers as bases instead of powers of two. For this problem, the terms of the Fibonacci sequence

算法题:UVa 11461 Square Numbers (简单数学)

11461 - Square Numbers Time limit: 1.000 seconds http://uva.onlinejudge.org/index.php? option=com_onlinejudge&Itemid=8&category=467&page=show_problem&problem=24 56 A square number is an integer number whose square root is also an integer.

UVa 10183 How Many Fibs? (统计斐波那契数个数&amp;amp;高精度)

10183 - How Many Fibs? Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=115&page=show_problem&problem=1124 Recall the definition of the Fibonacci numbers:    f1 := 1    f2 := 2    fn :