这样二分超时了两个案例 有佬教一下怎么优化吗
查看原帖
这样二分超时了两个案例 有佬教一下怎么优化吗
868135
zjczzx1314楼主2023/10/12 11:05
#include <iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
long long n;
int main()
{
	cin >> n;
	long long* a = new long long[n];
	long long* b = new long long[n];
	long long* c = new long long[n];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> b[i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> c[i];
	}
	sort(a, a + n);
	sort(b, b + n);
	sort(c, c + n);
	long long ans = 0;
	for (int i = 0; i<n; i++)
	{
		long long temp = a[i];
		int twol = -1, twor = n;
		while (twol + 1 != twor)
		{
			int mid = (twol + twor) >> 1;
			if (b[mid] > temp)
			{
				twor = mid;
			}
			else
			{
				twol = mid;
			}
		}
		if (twor == n)
		{
			break;
		}
		if (twor != n)
		{
			for (int i = twor; i < n; i++)
			{
				int temp = b[i];
				int threel = -1, threer = n;
				while (threel + 1 != threer)
				{
					int mid = (threel + threer) >> 1;
					if (c[mid] > temp)
					{
						threer = mid;
					}
					else
					{
						threel = mid;
					}
				}
				if (threer != n)
				{
					ans += n - threer;
				}
			}
		}
	}
	cout << ans << endl;
}

2023/10/12 11:05
加载中...