返回题解分享
讨论 / 题解分享/ 帖子详情

递增三元组(编程题) - 题解

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], b[N], c[N];
long long n,p,num1,num2,idx,num;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	for (int i = 1; i <= n; i ++ ) cin >> b[i];
	for (int i = 1; i <= n; i ++ ) cin >> c[i];
	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + n);
	sort(c + 1, c + 1 + n);
	/*
	for (int i = 1; i <= n; i ++ ) cout << a[i] << " ";
	cout << endl;
	for (int i = 1; i <= n; i ++ ) cout << b[i] << " ";
	cout << endl;
	for (int i = 1; i <= n; i ++ ) cout << c[i] << " ";
	cout << endl;
	*/
	for (int i = 1; i <= n; i ++ )
	{
		idx = 0;
		long long l = 1, r = n;
		while (l < r)
		{
			long long mid = l + r + 1 >> 1;
			if (a[mid] < b[i]) l = mid;
			else r = mid - 1;
		}
		num1 = l;
	    //cout << num1 << " ";
		l = 1, r = n;
		while (l < r)
		{
			long long mid = l + r >> 1;
			if (c[mid] > b[i]) r = mid;
			else l = mid + 1;
		}
		num2 = l;
		//cout << num2 << endl;
		
		if (a[num1] < b[i] && c[num2] > b[i])
		{
			idx =(num1 * (n - num2 + 1));
			num += idx;
		} 
		//cout << idx;
		
	}
	cout << num;
	return 0;
}
0 回复 0 转发 0 喜欢 1 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!