PTA L2-045 堆宝塔 (25 分)

这篇具有很好参考价值的文章主要介绍了PTA L2-045 堆宝塔 (25 分)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

PTA L2-045 堆宝塔 (25 分)
堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小,按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下:

  • 首先准备两根柱子,一根 A 柱串宝塔,一根 B 柱用于临时叠放。
  • 把第 1 块彩虹圈作为第 1 座宝塔的基座,在 A 柱放好。
  • 将抓到的下一块彩虹圈 C 跟当前 A 柱宝塔最上面的彩虹圈比一下,如果比最上面的小,就直接放上去;否则把 C 跟 B 柱最上面的彩虹圈比一下:
  • 如果 B 柱是空的、或者 C 大,就在 B 柱上放好;
  • 否则把 A 柱上串好的宝塔取下来作为一件成品;然后把 B 柱上所有比 C 大的彩虹圈逐一取下放到 A 柱上,最后把 C 也放到 A 柱上。

重复此步骤,直到所有的彩虹圈都被抓完。最后 A 柱上剩下的宝塔作为一件成品,B 柱上剩下的彩虹圈被逐一取下,堆成另一座宝塔。问:宝宝一共堆出了几个宝塔?最高的宝塔有多少层?

输入格式:

输入第一行给出一个正整数 N ( ≤ 1 0 3 ) N(≤10^3) N103,为彩虹圈的个数。第二行按照宝宝抓取的顺序给出 N N N 个不超过 100 100 100 的正整数,对应每个彩虹圈的直径。

输出格式:

在一行中输出宝宝堆出的宝塔个数,和最高的宝塔的层数。数字间以 1 个空格分隔,行首尾不得有多余空格。

输入样例:
11
10 8 9 5 12 11 4 3 1 9 15
输出样例:
4 5
样例解释:

宝宝堆成的宝塔顺次为:文章来源地址https://www.toymoban.com/news/detail-423667.html

  • 10、8、5
  • 12、11、4、3、1
  • 9
  • 15、9
#include<bits/stdc++.h>
using namespace std;

int main()
{
	vector<vector<int>> res;
	vector<int> a,b;

	int n;cin>>n;
	while(n--)
	{
		int x;cin>>x;
		if(a.empty()) a.push_back(x);//如果 A 为空,先放一个
		else if(x<a.back()) a.push_back(x);//如果比 A 最上面的小,就直接放上去
		else if(b.empty()||x>b.back()) b.push_back(x);//如果 B 柱是空的、或者 C 大,就在 B 柱上放好;
        else
        {
            res.push_back(a);a.clear();// A 记作一件成品
            while(!b.empty()&&b.back()>x) // 把 B 柱上所有比 C 大的彩虹圈逐一取下放到 A 柱上
            {
                a.push_back(b.back());
                b.pop_back();
            }
            a.push_back(x); // 最后把 C 也放到 A 柱上。
        }
	}

	if(!a.empty()) res.push_back(a);
	if(!b.empty()) res.push_back(b);

	int mx=0;
	for(auto &c:res)
		mx=max(mx,(int)c.size());
	cout<<(int)res.size()<<" "<<mx;

	return 0;
}

到了这里,关于PTA L2-045 堆宝塔 (25 分)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包