xdoj 1068 两组数相乘第k大

2019-07-09 by fffasttime·0评论

把相乘列成矩阵，首先想到可以二分答案，然后根据答案再二分出每行的位置。但是这样是这样对大数据有压力。然后因为答案在矩阵中的位置是单调的，所以扫一次即可，O(nlogn)。

```
/*
```
```
Author: fffasttime
```
```
Date: 
```
```
*/
```
```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
typedef long long ll;
```
```
#define inc(i,n) for (int i=0;i<n;i++)
```
```
const int N=100010;
```
```
 
```
```
ll a[N],b[N];
```
```
 
```
```
int n,m,k;
```
```
 
```
```
bool check(ll s){
```
```
	int r=m-1,sum=0;;
```
```
	for (int i=0;i<n;i++){
```
```
		for (;r>=0 && a[i]*b[r]<=s;r--);
```
```
		sum+=r+1;
```
```
	}
```
```
	return sum<k;
```
```
}
```
```
 
```
```
int main(){
```
```
	int T; cin>>T;
```
```
	while (T--){
```
```
		cin>>n>>m>>k;
```
```
		inc(i,n) scanf("%lld",a+i);
```
```
		inc(i,m) scanf("%lld",b+i);
```

		sort(a,a+n,greater<ll>()); sort(b,b+m,greater<ll>());

```
		ll l=0,r=1e11;
```
```
		while (l<r){
```
```
			ll mid=l+r>>1;
```
```
			if (check(mid)) r=mid;
```
```
			else l=mid+1;
```
```
		}
```
```
		printf("%lld\n",r);
```
```
	}
```
```
	return 0;
```
```
}
```

发表评论取消回复