hxdm,求问有没有可能在n<=3e6的情况下卡掉严格O(n)算法
查看原帖
hxdm,求问有没有可能在n<=3e6的情况下卡掉严格O(n)算法
197149
夜枭只会舔fufu楼主2022/3/27 19:50
#include<iostream>
#include<map>
#include<algorithm>
#include<cstdio>
using namespace std;
struct edd
{
	long long a,b;
}t[3000001];
map<long long,bool> s;
bool cmp(edd a,edd b)
{
	if(a.a==b.a)
	{
		return a.b<b.b;
	}
	return a.a<b.a;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld %lld",&t[i].a,&t[i].b);
	}
	long long ans=n+1;
	for(int i=1;i<=n;i++)
	{
		if(!s[t[i].a-t[i].b]||!s[t[i].a+t[i].b])
		{
			s[t[i].a-t[i].b]=1;
			s[t[i].a+t[i].b]=1;
		}
		else
		{
			ans++;
		}
	}
	cout<<ans;
	return 0;
 } 

这是代码

2022/3/27 19:50
加载中...