为什么O(N^2)会超时啊?
查看原帖
为什么O(N^2)会超时啊?
739515
wc3624762194楼主2025/2/4 14:52

TLE on 4,8,10,14,15,18,剩下的基本都10ms以内过了https://www.luogu.com.cn/record/201256413

#include<bits/stdc++.h>
#include<time.h>
using namespace std;
#define ll long long
const int N = 1e4;
const int MOD = 1e9 + 7;
ll a[N], b[N];
ll ap[N], bp[N];//哪个数字
int aq[N], bq[N]; //出现了几次
int suma, sumb;
map<ll, int>vo;
queue<ll>fin;
int main()
{
	int n, m;
	cin >> n;
	m = n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		cin >> b[i];
	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + n);
	//将同样的数字分段,并标记有多少个
	for (int i = 1; i <= n; i++)
	{
		int len = 1;
		while (a[i + 1] == a[i]) i++, len++;
		suma++;
		ap[suma] = a[i];
		aq[suma] = len;
	}
	for (int i = 1; i <= n; i++)
	{
		int len = 1;
		while (b[i + 1] == b[i]) i++, len++;
		sumb++;
		bp[sumb] = b[i];
		bq[sumb] = len;
	}
	for (int i = 1; i <= suma; i++)
	{
		for (int j = 1; j <= sumb; j++)
		{
			ll mix = (ap[i] * bp[j]) % MOD;
			if (vo[mix] == 0) fin.push(mix);
			vo[mix] += min(aq[i], bq[j]);
		}
	}
	int ans = 0;
	while (!fin.empty())
	{
		ll x = fin.front();
		fin.pop();
		ans = max(ans, vo[x]);
	}
	cout << ans;
	return 0;
}
2025/2/4 14:52
加载中...