点击打开链接
题目意思: 这一题题目真心不好看懂,所以呢,我就大概描述一下,题目是说有一个娃娃大小为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;
}
分享到:
相关推荐
GeneralizedDiscriminantAnalysis
Lions-Generalized_Solutions_of_Hamilton-Jacobi_Equations.djvu
中断概率矩阵代码认知网络中广义局部继电器选择协议的保密性能 这是以下文章的Matlab代码:“底层认知网络中的通用部分中继选择协议的保密性能”,《国际通信系统杂志》,第1卷。 31号17卷,第1-17页,2018年11月。...
字符型数据的通用格式保留加密方案,马昊玉,刘哲理,本文主要研究了字符型数据的格式保留加密(FPE)问题,以期寻求一种可以同时保留字符串长度和存储占用的FPE方案。通过将不同字符根��
北京大学使用深度展开神经网络在图像去雾、去噪和压缩感知方向上取得了最好的结果。深度展开神经网络是一种深度学习模型,它通过多层神经网络来学习输入数据的特征表示。在图像去雾方向上,深度展开神经网络可以通过...
Solving XOR-problem and consecutively try MNIST-dataset with fundamental level of understanding on neural networks. Recommendable for beginners ( As I am :) ) And it s fully documented.
基于快速广义互相关时延估计算法的深度测量技术
Hastie的经典著作, 可加模型, 想快速了解可加模型以及广义可加模型直接阅读2,4,6章
理解广义学习模型的成员推论 Understanding Membership Inferences on Well-Generalized Learning Models 中文翻译
广义互相关时延估计,瑞利限广义互相关时延估计,瑞利限广义互相关时延估计,瑞利限
α-generalized resolution principle based on the lattice-valued first-order logic system
Convergence of general algorithm for I-generalized asymptotically nonexpansive nonself-mappings in uniformly convex hyperbolic spaces
An Intelligent Algorithm for the (1,2,2)-Generalized Knight's Tour Problem
IETF--通用分段路由报头 IETF草案:通用段路由标头
最佳优先广义规划用于搜索通常可以解决计划问题的程序的启发式和评估技术。 该框架使用领域特定的语言通过计数器,常量指针,指针和内存寄存器进行规划。 它从一个简短的教程开始,然后稍后详细解释每个步骤。...
BlendedMVS - A Large-Scale Dataset for Generalized Multi-View St
Matlab降为300个特征的代码单一输入的广义回归神经网络集成 该项目使用针对未标记的数值数据集的广义回归神经网络,针对缺失数据的单次插补处理MATLAB代码的开发。 不完整的数据集将分为完整和不完整的数据集。...
广义地图和归约实验室 学习目标 识别使用块可以避免的重复 陈述构造块的两种方法 从方法内执行块 说明yield关键字的目的 在方法和块之间传递数据 介绍 如您在上一课中所看到的,在我们各种基于map的方法和基于reduce...
广义地图和归约实验室学习目标识别使用块可以避免的重复陈述构造块的两种方法从方法内执行块说明yield关键字的目的在方法和块之间传递数据介绍如您在上一课中所看到的,在我们各种基于map的方法和基于reduce的方法...
广义地图和归约实验室 学习目标 识别使用块可以避免的重复 陈述构造块的两种方法 从方法内执行块 说明yield关键字的目的 在方法和块之间传递数据 介绍 如您在上一课中所看到的,在我们各种基于map的方法和基于reduce...