有没有大佬来分析个复杂度?
查看原帖
有没有大佬来分析个复杂度?
330888
Colala楼主2021/10/23 22:05

考后自己思考后口胡的做法,洛谷A了。至于考试时,全程梦游啥都不会,

#include<bits/stdc++.h>
using namespace std;
#define MAX 100005

struct Node{
	int a;
	int b;
}x[MAX];
bool operator <(const Node &a, const Node &b) {return a.a < b.a;}

int ans[MAX][2], n, m0, m1, fa[MAX];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}

int search(int l, int r, int b)
{
	int mid, ret = r + 1;
	while(l <= r)
	{
		mid = (l + r) / 2;
		if(x[mid].a < b) l = mid + 1;
		else r = mid - 1, ret = mid;
	}
	return ret;
}

void work(int m, int T)
{
	memset(fa, 0, sizeof(fa));
	memset(x, 0, sizeof(x));
	for(int i = 1;i <= m + 1;++i) fa[i] = i;
	for(int i = 1;i <= m;++i) cin >> x[i].a >> x[i].b;
	sort(x + 1, x + m + 1);
	x[m + 1].a = 0x7fffffff;
		
	for(int i = 1;i <= n;++i)
	{
		int p = find(1);
		while(p <= m)
		{
			++ans[i][T];
			fa[p] = p + 1;
			p = find(search(find(p), m + 1, x[p].b));
		}
	}
	for(int i = 1;i <= n;++i) ans[i][T] += ans[i - 1][T];
}


int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m0 >> m1;
	work(m0, 0);
	work(m1, 1);
	int ret = 0;
	for(int i = 0;i <= n;++i) ret = max(ret, ans[i][0] + ans[n - i][1]);
	cout << ret;
	return 0;
}
2021/10/23 22:05
加载中...