CF912E 题解

ikunTLE · 2025-09-14 18:00:13 · 题解

思路

先想暴力思路：可以 dfs 枚举每一个数的幂，然后将所有 <10^{18} 的数全部存起来，排序求第 k 大。

优化考虑折半搜索：将 n 个整数分成两个组，尽量让这两个组数据比较平均。按照上述暴力思路可以分别求出两个组别的所有情况，然后排序。

得到了这样两个序列 A_1 和 A_2，仍然没法直接求第 k 大是几，但是可以求一个数 X 是第几大：通过双指针，一个指针 i 从左到右遍历第一个序列；另一个指针 j 从右往左遍历第二个序列，求 A_{1,i}\times A_{2,j}<X 的最大 j。统计所有 j 左边有多少数的和即为所求。

最后易想到通过二分求 k 的值。

注意事项

• 乘法时注意不要炸掉 long long。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int INF=1e18;
vector<int>x[5],a[5];
void dfs(int id,int u,int n,int sum){
    if(u>=n){
        if(sum<=INF)
            a[id].push_back(sum);
        return;
    }
    dfs(id,u+1,n,sum);
    while(true){
        if((__int128)sum*x[id][u]>INF)
            return;
        sum*=x[id][u];
        dfs(id,u+1,n,sum);
    }
    return;
}
int calc(int k){
    int i=0,j=(int)a[2].size()-1,res=0;
    while(i<(int)a[1].size()&&j>=0){
        if((__int128)a[1][i]*a[2][j]<k){
            res+=j+1;
            ++i;
        }
        else --j;
    }
    return res;
}
signed main(){
    int n=read(),sum1=1,sum2=1;
    for(int i=1;i<=n;++i){
        int num=read();
        if(sum1<=sum2){
            x[1].push_back(num);
            sum1*=num;
        }
        else{
            x[2].push_back(num);
            sum2*=num;
        }
    }
    sort(x[1].begin(),x[1].end());
    sort(x[2].begin(),x[2].end());
    dfs(1,0,(int)x[1].size(),1);
    dfs(2,0,(int)x[2].size(),1);
    sort(a[1].begin(),a[1].end());
    sort(a[2].begin(),a[2].end());
    int k=read();
    int l=1,r=1e18;
    while(l<=r){
        int mid=(l+r)>>1;
        if(calc(mid)<k)
            l=mid+1;
        else r=mid-1;
    }
    printf("%lld\n",r);
    return 0;
}