---

D. Coprime(掐时间复杂度点，思维题，贪心)

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

题目：

cobol<br/>6<br/>3<br/>3 2 1<br/>7<br/>1 3 5 2 4 7 7<br/>5<br/>1 2 3 4 5<br/>3<br/>2 2 4<br/>6<br/>5 4 3 15 12 16<br/>5<br/>1 2 2 3 6<br/>

cobol<br/>6<br/>12<br/>9<br/>-1<br/>10<br/>7<br/>

思路：

这是一道思维题，也有贪心，暴力枚举，在这里是掐着时间复杂度的思维题。

题目意思是 从数组中 找出互质的两个数 它们的下标最大。

所以我们可以在输入的时候标记一下对应元素的下标，然后是顺着标记，这样也是贪心，当出现相同的元素，我们取最大的下标覆盖之前标记的最小下标

又因为 这里元素数据范围是 1000 即（10^3）这里我们再进行两层循环 时间复杂度是 10^6 加上我们的 __gcd ()时间复杂度O(log min(a，b))，最坏情况nlog min(a,b)，测试样例 1 <= T <= 10 数据范围 ,我们用 unordered_map 时间复杂度是 O(1),最坏的情况也是 O(n) 这里的 n 是我们的元素数据范围 1000

整个循环过程,时间复杂度就是10^7 + 1000 + nlog min(a,b)——10^8 + 1000 + nlog min(a,b)之间

没有超过 10^9 所以不会超时，一般来说 超过 10^9 就会超时的

代码详解如下：

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

inline void solve()
{

	umap<int, int>r;
	// r 用来标记元素对应的下标
	// 用 unordered_map 效率为 O(1)
	int n = 0;
	int ans = -1;
	cin >> n;
	for (int i = 1, x; i <= n; ++i)
	{
		cin >> x;
		// 标记好下标
		r[x] = i;
	}
	// 因为我们元素的数据范围为 1000 所以直接暴力两层循环
	// 查找我们下标和最大即可  这里的两层循环 效率为 O(n^2)  所以 O(1000 * 1000 == 1e6)
	// 这样是不会超时的，反而如果 用 我们定义的 n  则 O((2 * 1e5) * (2 * 1e5) == 4 * 1e10)就会超时了
	// 再加上 __gcd() 时间复杂度是 O(log min(a，b)) 可以刚刚恰着TLE分界线，差一丢丢就会超时的
	// 这是贪心思维题

	for (int i = 1; i <= 1000; ++i)
	{
		for (int j = 1; j <= 1000; ++j)
		{
			if (__gcd(i, j) == 1 && r[i] && r[j])
			{
				ans = max(ans, r[i] + r[j]);
			}
		}
	}
	cout << ans << endl;
}

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

	return 0;
}

最后提交: