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

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

#### 二分

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N  = 1e5+100;
int a[N],b[N],c[N];

int main(){
	int n;
	cin >> 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);
	ll ans =0;
	for(int i=0;i<n;i++){
		ll x =lower_bound(a,a+n,b[i])-a;
		ll y =n-(upper_bound(c,c+n,b[i])-c);
		ans +=x*y;
	}
	cout << ans << endl; 
}


ll x = lower_bound(a,a+n,b[i])-a;: 这里使用lower_bound函数在排序后的数组a中找到第一个不小于b[i]的元素的位置。然后,从这个位置减去数组a的起始位置a,得到的x是数组a小于b[i]的元素的数量。
ll y = n-(upper_bound(c,c+n,b[i])-c);: 这里使用upper_bound函数在排序后的数组c中找到第一个大于b[i]的元素的位置。从n减去这个位置与数组c起始位置的差,得到的y是数组c大于b[i]的元素的数量。
* ans += x*y;: 最后,计算xy的乘积,并累加到ans上。这个乘积实际上是对于每个b[i],在a中小于它的元素数量与在c中大于它的元素数量的组合。
0 回复 0 转发 1 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!