C++菜鸡用的优化版dfs tle了,有大神教下怎么分析时间复杂度吗
查看原帖
C++菜鸡用的优化版dfs tle了,有大神教下怎么分析时间复杂度吗
571939
A_pier楼主2021/11/1 19:16
#include<iostream>
#include<algorithm>
using namespace std;

struct match
{
	int b, e;
};

bool cmp(match a, match bb)
{
	return a.b < bb.b;
}

match m[1000001];
int ans = 0, num = 0;
int n;

void dfs(int startx, int en)
{
	for (int i = startx; i < n ; i++) {
		if (en <= m[i].b) {
			num++;
			if (ans < num)
				ans = num;
			dfs(i + 1, m[i].e);
			num--;
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> m[i].b >> m[i].e;
	}
	sort(m, m + n, cmp);
	dfs(0, 0);

	cout << ans << endl;

	return 0;
}
2021/11/1 19:16
加载中...