关于此代码时间复杂度
查看原帖
关于此代码时间复杂度
546289
Link_Cut_qwq楼主2021/8/1 21:03

这不是代码复杂度不是 o(Tnlogn)o(Tnlogn) 吗?为啥只有70分?(剩下的全T)

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

struct Node
{
	int x, u, t;
};
struct cm1
{
	bool operator()(Node a, Node b) 
	{
		if (a.x != b.x) return a.x < b.x;
		else return a.u < b.u;
	}
};
struct cm2
{
	bool operator()(Node a, Node b) {
		if (a.x != b.x) return a.x > b.x;
		else return a.u > b.u;
	}
};

priority_queue <Node, vector <Node>, cm1> qx; //大根堆 
priority_queue <Node, vector <Node>, cm2> qi; //小根堆 

int n, m, a[1000100], f[1000100][3], ch[1000100], num, las, T, id, x, nm;
bool del[2000100];

void cln ()
{
	while (!qx.empty ()) qx.pop ();
	while (!qi.empty ()) qi.pop ();
	memset (ch, 0, sizeof (ch));
	memset (del, 0, sizeof (del));
}

int main ()
{
	cin >> T;
	for (int l = 1; l <= T; l++)
	{
		if (l == 1)	
		{
			cin >> n;
			for (int i = 1; i <= n; i++) cin >> a[i];
		} else	
		{
			cin >> m;
			for (int i = 1; i <= m; i++)
			{
				cin >> id >> x;
				a[id] = x;
			}
		}
		cln ();
		for (int i = 1; i <= n; i++)
		{
			Node p = {a[i], i, i};
			qx.push (p), qi.push (p); 
		}
		for (int i = 1; i < n; i++)
		{
			while (!qx.empty () && del[qx.top ().t]) qx.pop ();
			del[qx.top ().t] = 1; f[i][1] = qx.top ().u;
			while (!qi.empty () && del[qi.top ().t]) qi.pop ();
			del[qi.top ().t] = 1; f[i][2] = qi.top ().u;
			Node p = {qx.top ().x - qi.top ().x, qx.top ().u, i + n};
			qx.push (p); qi.push (p); 
		}
		num = 1, las = n - 1;
		for (int i = n - 1; i >= 1; i--)
		{
			if (ch[f[i][1]] == num)
			{
				las = i - 1; num++;
			} else ch[f[i][2]] = num;
		}
		cout << n - las << endl;
	}
	return 0;
}

2021/8/1 21:03
加载中...