---

F. We Were Both Children

原创 已于 2023-08-12 02:16:25 修改 · 粉丝可见 · 188 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132219379

题目：

cobol<br/>7<br/>5<br/>1 2 3 4 5<br/>3<br/>2 2 2<br/>6<br/>3 1 3 4 9 10<br/>9<br/>1 3 2 4 2 3 7 8 5<br/>1<br/>10<br/>8<br/>7 11 6 8 12 4 4 8<br/>10<br/>9 11 9 12 1 7 2 5 8 10<br/>

cobol<br/>3<br/>3<br/>3<br/>5<br/>0<br/>4<br/>4<br/>

思路:

这里就是暴力模拟一遍，不同的是，要用 umap 来模拟每只青蛙跳跃在 n 范围内

所以我一开始一直用vector和 数组 啥的，一直 TLE 不知道为啥 (;´༎ຶД༎ຶ`)

然后找到对应的 坐标累加有多少只青蛙跳到这，然后取出 最多青蛙在同一坐标数量，就是我们捕获到的最多青蛙

代码详解如下：

#include <iostream>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define umap unordered_map
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;

inline void solve()
{
	int n = 0;

	umap<int, int>a;	// a 数组为我们青蛙跳跃的记录

	umap<int, int>r;	// r 为各个点的坐标，我们青蛙跳到这个坐标总共有多少只

	cin >> n;
	for (int i = 0, x; i < n; ++i)
	{
		cin >> x;
		if (x > n)
		{
			// 如果一开始就跳跃超出范围了
			// 我们就不遍历这一只青蛙
			continue;
		}

		// 这里是 以 map 中 x 为 青蛙跳跃长度  y 为青蛙数量
		// 用 umap 不用 vector 是因为用 vector 的话还要 PII
		// 而我们 用 umap 效率高，查询速度是 O(1)	方便省去了定义 PII
		// 还要注意这里为什么要用 ++ 是因为 万一有跳跃长度相同的青蛙呢
		a[x]++;
	}


	int ans = 0;	// ans 为我们答案捕获青蛙的数量

	// 开始模拟跳跃
	for (auto &i : a)
	{
		// now 为我们青蛙现在跳跃到的坐标
		int now = i.x;

		// 如果跳跃后所在的坐标在范围内
		// 我们开始统计该坐标到达的数量
		while (now <= n)
		{
			// r 开始记录到这个坐标的青蛙总和
			r[now] += i.y;

			// 查找所有坐标中数量最多的青蛙，就是我们得到最多的青蛙
			if (ans < r[now])
				ans = r[now];

			// 开始跳跃
			now += i.x;
		}
	}

	cout << ans << endl;
	return;
}

int main()
{
	___G;
	int _t;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}

最后提交：