ABC-391-F - K-th Largest Triplet · znzryb
## 思路讲解
这个第一个贪心做法我觉得有点玄学，当然也敲了一遍，下面的第一个就是二分法
有些时候，你发现一个问题可以排序，这个时候就非常有可能是二分答案了
二分答案就是要剪枝，而且一旦发现rank ≥ m就立即返回，不要犹豫（也算是一种剪枝）
```cpp
inline bool check(ll x){
ll rank=0;
FOR(i,1,N){
if(f(i,1,1)<x) break;
FOR(j,1,N){
if(f(i,j,1)<x) break;
FOR(k,1,N){
if(f(i,j,k)<x) break;
++rank;
if(rank>=M) return true;
}
}
}
// deEnter(rank);
// if(rank>=M) return true;
return false;
}
```
## AC代码
[https://atcoder.jp/contests/abc391/submissions/62332464](https://atcoder.jp/contests/abc391/submissions/62332464)
```cpp
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define deSpace(x) cerr<<x<<' '
#define deEnter(x) cerr<<x<<'\n'
using namespace std;
typedef unsigned long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(2e5)+10,MAXval=static_cast<ll>(1e18)+3;
ll N,M,A[5][MAXN];
struct Triple{
ll val,i,j,k;
};
struct cmp{
bool operator()(const Triple &a,const Triple &b) const{
return a.val<b.val;
}
};
struct cmpSet{
bool operator()(const Triple &a,const Triple &b) const{
if(a.val!=b.val) return a.val<b.val;
if(a.i!=b.i) return a.i<b.i;
if(a.j!=b.j) return a.j<b.j;
if(a.k!=b.k) return a.k<b.k;
return false;
}
};
priority_queue<Triple,vector<Triple> ,cmp> pq;
set<Triple,cmpSet> vis;
ll f(ll i,ll j,ll k){
ll res=0;
res=A[1][i]*A[2][j]+A[1][i]*A[3][k]+A[2][j]*A[3][k];
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N>>M;
FOR(i, 1, 3){
FOR(j,1,N){
cin>>A[i][j];
}
sort(&A[i][1],&A[i][N+1],greater<ll>());
}
ll rank=0;
pq.push((Triple){f(1,1,1),1,1,1});
while(!pq.empty()){
++rank;
// deSpace(pq.top().val);deSpace(pq.top().i);deSpace(pq.top().j);deEnter(pq.top().k);
if(rank==M){
cout<<pq.top().val<<'\n';
return 0;
}
ll i=pq.top().i,j=pq.top().j,k=pq.top().k;
pq.pop();
if(vis.find((Triple){f(i+1,j,k),i+1,j,k})==vis.end() && i+1<=N){
pq.push((Triple){f(i+1,j,k),i+1,j,k});
vis.insert((Triple){f(i+1,j,k),i+1,j,k});
}
if(vis.find((Triple){f(i,j+1,k),i,j+1,k})==vis.end() && j+1<=N){
pq.push((Triple){f(i,j+1,k),i,j+1,k});
vis.insert((Triple){f(i,j+1,k),i,j+1,k});
}
if(vis.find((Triple){f(i,j,k+1),i,j,k+1})==vis.end() && k+1<=N){
pq.push((Triple){f(i,j,k+1),i,j,k+1});
vis.insert((Triple){f(i,j,k+1),i,j,k+1});
}
}
return 0;
}
/*
AC
https://atcoder.jp/contests/abc391/submissions/62332464
*/
```
[https://atcoder.jp/contests/abc391/submissions/62335145](https://atcoder.jp/contests/abc391/submissions/62335145)
二分法
```cpp
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define deSpace(x) cerr<<x<<' '
#define deEnter(x) cerr<<x<<'\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(2e5)+10,MAXval=static_cast<ll>(3e18)+3;
ll N,M,A[MAXN],B[MAXN],C[MAXN];
ll f(ll i,ll j,ll k){
ll res=A[i]*B[j]+A[i]*C[k]+B[j]*C[k];
return res;
}
inline bool check(ll x){
ll rank=0;
FOR(i,1,N){
if(f(i,1,1)<x) break;
FOR(j,1,N){
if(f(i,j,1)<x) break;
FOR(k,1,N){
if(f(i,j,k)<x) break;
++rank;
if(rank>=M) return true;
}
}
}
// deEnter(rank);
// if(rank>=M) return true;
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>N>>M;
FOR(i, 1, N){
cin>>A[i];
}
FOR(i, 1, N){
cin>>B[i];
}
FOR(i, 1, N){
cin>>C[i];
}
sort(&A[1],&A[N+1],greater<ll>());
sort(&B[1],&B[N+1],greater<ll>());
sort(&C[1],&C[N+1],greater<ll>());
// 使用二分查找到正好有K(M)个数比它大的数（也就是第K个）
ll l=0,r=MAXval;
while(l<r){
ll mid=l+r+1>>1;
if(check(mid)){
l=mid;
}else{
r=mid-1;
}
}
cout<<l<<'\n';
return 0;
}
/*
AC
https://atcoder.jp/contests/abc391/submissions/62335145
*/
```
## 心路历程（WA，TLE，MLE……）