求分析时间复杂度
  • 板块学术版
  • 楼主caramel_qwq
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/7/29 09:56
  • 上次更新2023/10/27 17:54:49
查看原帖
求分析时间复杂度
444195
caramel_qwq楼主2022/7/29 09:56

求大佬帮忙分析时间复杂度,另外提个问题

如果n,m,k最大可到10510^5,1.0s内会超时嘛?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
vector<ll> a,b,c;
set<ll> st;
int main(){
	freopen("twothree.in","r",stdin);
	freopen("twothree.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		ll num;
		scanf("%lld",&num);
		a.push_back(num);
	}
	for(int i=1;i<=m;i++){
		ll num;
		scanf("%lld",&num);
		b.push_back(num);
	}
	for(int i=1;i<=k;i++){
		ll num;
		scanf("%lld",&num);
		c.push_back(num);
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	sort(c.begin(),c.end());
	for(int i=0;i<max(n,max(m,k));i++){
		vector<ll>::iterator it1,it2,it3;
		if(n>=i){
			it1=find(a.begin(),a.end(),a[i]);
			it2=find(b.begin(),b.end(),a[i]);
			it3=find(c.begin(),c.end(),a[i]);
			bool flag1=bool((it1!=a.end()&&it2!=b.end())||(it1!=a.end()&&it3!=c.end())||(it2!=b.end()&&it3!=c.end()));
			if(flag1==true) st.insert(a[i]);
		}
		if(m>=i){
			it1=find(a.begin(),a.end(),b[i]);
			it2=find(b.begin(),b.end(),b[i]);
			it3=find(c.begin(),c.end(),b[i]);
			bool flag2=bool((it1!=a.end()&&it2!=b.end())||(it1!=a.end()&&it3!=c.end())||(it2!=b.end()&&it3!=c.end()));
			if(flag2==true) st.insert(b[i]);
		}
		if(k>=i){
			it1=find(a.begin(),a.end(),c[i]);
			it2=find(b.begin(),b.end(),c[i]);
			it3=find(c.begin(),c.end(),c[i]);
			bool flag3=bool((it1!=a.end()&&it2!=b.end())||(it1!=a.end()&&it3!=c.end())||(it2!=b.end()&&it3!=c.end()));
			if(flag3==true) st.insert(c[i]);
		}
	}
	for(set<ll>::iterator it=st.begin();it!=st.end();it++){
		printf("%lld ",*it);
	}
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}
2022/7/29 09:56
加载中...