STL总结

目录

例题1 宝藏排序II

题目描述

输入描述

输出描述

解

结果

例题2 小蓝吃糖果

题目描述

输入描述

输出描述

输入输出示例

分析

解

结果

例题3 小蓝的括号串

题目

解

例题4 快递分拣

题目描述

输入描述

输出描述

输入输出样例

示例输入

样例输出

解

---

用四个题目检验一下前面所学的知识

例题1 宝藏排序II

题目描述

在一个神秘的岛屿上，有一支探险队发现了一批宝藏，这批宝藏是以整数数组的形式存在的。每个宝藏上都标有一个数字，代表了其珍贵程度。然而，由于某种神奇的力量，这批宝藏的顺序被打乱了，探险队需要将宝藏按照珍贵程度进行排序，以便更好地研究和保护它们。作为探险队的一员，肖恩票要设计合适的排序算法来将宝藏按照珍贵程度进行从小到大排序。请你帮帮肖恩。

输入描述

输入第一行包括一个数字n，表示宝藏总共有n个
输入的第二行包括n个数字，第个数a表示第个宝藏的珍贵程度
数据保证1<n<10^5,1<a[i]< 10^9

输出描述

输出n个数字，为对宝藏按照珍贵程度从小到大排序后的数组

解

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 3;
int a[N];
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	sort(a+1, a + 1 + n);
	for (int i = 1; i <= n; i++)
	{
		cout << a[i] << " \n"[i==n];
	}
	return 0;
}

结果

5
2 5 4 6 1
1 2 4 5 6

例题2 小蓝吃糖果

题目描述

小蓝有n种糖果，每种数量已知。

小蓝不喜欢连续吃2次一样的糖果。问有没有可行的吃糖方案。

输入描述

第一行是整数(0<n<1000000)

第二行包含n个数，表示n种糖果的数量mi，0<mi<1000000

输出描述

输出一行，包含一个Yes或no。

输入输出示例

输入：

3

4 1 1

输出：

No

分析

只需满足糖果总数 大于 最多类型糖果数量-1；因为在最多数量糖果之间的间隙中插入其他糖果，如果糖果总数-最多类型的糖果数量大于间隙数，肯定能满足，因为间隙只会越来越多

解

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
using ll = long long;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	priority_queue<int>pq;
	ll sum = 0;
	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		pq.push(x);
		sum += x;
	}
	ll mx = pq.top();

	if (sum - mx >= mx - 1)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	
	return 0;
}

结果

3
4 1 1
No

例题3 小蓝的括号串

题目

解

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
using ll = long long;
stack<char>stk;
const int N = 100;
char s[N];
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin >> n;
	cin >> s + 1;
	bool ans = true;
	for (int i = 1; i <= n; i++)
	{
		if (s[i] == '(')
		{
			stk.push('(');//入栈
		}
		else
		{
			if (stk.size()&&stk.top() == '(')
			{
				stk.pop();
			}
			else
			{
				ans = false;
			}
		}
	}
	if (stk.size())
	{
		ans = false;
	}
	if (ans)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	
	return 0;
}

例题4 快递分拣

题目描述

蓝桥王国的每个快递都包含两个参数：1.快递单号 2.快递城市。

小李是蓝桥王国的一名快递员，每天的快递分拣让他苦不堪言。

于是他想要你帮他设计一个程序用于快递的分拣（将不同快递按城市信息分开）。

输入描述

输入第一行包含一个整数 N,表示快递的个数。

接下来第2-n+1行每行包含一个字符串S和一个字符串P，分别快递单号和快递对应的城市

1<=N<=10^3,保证数量不超过10^6.

输出描述

输出共若干行。按城市的输入顺序依次输出城市的名称以及城市的快递个数，以及该城市的所有快递单号（单号按照输入顺序排序）。

输入输出样例

示例输入

10
10124214 北京
12421565 上海
sdafasdg213 天津
fasdfga124 北京
145252 上海
235wtdfsg 济南
3242356fgdfsg 成都
23423 武汉
23423565f 沈阳
1245dfwfs 成都

样例输出

北京 2
10124214
fasdfga124
上海 2
12421565
145252
天津 1
sdafasdg213
济南 1
235wtdfsg
成都 2
3242356fgdfsg
1245dfwfs
武汉 1
23423
沈阳 1
23423565f

解

#include<iostream>
#include<map>
#include<vector>
using namespace std;
map<string, vector<string>>mp;
vector<string>citys;
int main()
{
	ios::sync_with_stdio, cin.tie(0), cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
	{
		string a, b; cin >> a >> b;//数字 城市

		if (!mp.count(b))//b城市没出现过
		{
			citys.push_back(b);
		}
		mp[b].push_back(a);//城市 数字
	}
	for (const auto& city : citys)
	{
		cout << city << ' ' << mp[city].size() << endl;
		for (const auto& i : mp[city])
		{
			cout << i << endl;
		}
	}
	return 0;
}