求助,AC了,但是不知道时间复杂度是多少
查看原帖
求助,AC了,但是不知道时间复杂度是多少
1215295
discretely楼主2024/3/31 20:25
// Problem: 
//     P1631 序列合并
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1631
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int main(){
	int n;cin>>n;
	vector<int> a(n+1);
	vector<int> b(n+1);
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i) cin>>b[i];
	priority_queue<int> q;
	for(int i=1;i<=n;++i){
		q.push(a[1]+b[i]);
	}
	for(int i=2;i<=n;++i){
		for(int j=1;j<=n;++j){
			if(a[i]+b[j]>=q.top()) break;
			else q.push(a[i]+b[j]),q.pop();
		}
	}
	vector<int> c(n+1);int cnt=0;
	while(q.size()){
		c[++cnt]=q.top();q.pop();
	}
	for(int i=n;i>=1;--i) cout<<c[i]<<' ';
	
	return 0;
}
2024/3/31 20:25
加载中...