dalao 请问如何缩小时间复杂度
查看原帖
dalao 请问如何缩小时间复杂度
129390
yangwenbin楼主2020/9/29 10:06
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1e5 + 50;

inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')
		{
			f = -1;
		}
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	x = f * x;
	return x;
}

int n,ans;
int shoe[SIZE << 1],indax[SIZE << 1];
bool vis[SIZE << 1];

int main()
{
	n = read();
	for (int i = 0; i < n; ++i)
	{
		shoe[i << 1] = read();
		indax[i << 1] = i << 1;
		shoe[(i << 1) + 1] = read();
		indax[(i << 1) + 1] = (i << 1) + 1;
	}
	for (int i = 0; i < (n << 1); ++i)
	{
		if (vis[i]) continue;
		for (int j = i+1; j < (n << 1); ++j)
		{
			if (vis[j]) continue;
			if (abs(shoe[i]) != abs(shoe[j]))
			{
				indax[j] ++ ;
				continue;
			}
			ans += (indax[j] - indax[i] - (shoe[j] > 0 ? 1 : 0));
			vis[i] = vis[j] = true;
			break;
		}
	}
	printf("%d\n",ans);
	return 0;
}

2020/9/29 10:06
加载中...