本文最后更新于:2020年4月13日 早上

题目简述

  • 您将获得一个像100个单元格计算单元格。
  • 找出第K个乘积的值,并计算较小的乘积。

题目分析

假设答案为中,则答案为最小的中数,其个数小于或等于$K$且大于或等于$K$。如果增加$mid$的值,则乘积超过$mid$的乘积也会单调增加,从而可以通过二分查找来解决$mid$的值。计算第mid行以下数字的方法在第i行中相乘,并且$mid$以下行的数字为$ai * bj <= mid$,即$bj <= mid / ai$。

因此,可以通过检查$b$中的$mid / ai$数来理解。如果对$b$进行排序,则可以通过二进制搜索快速获得数字。以此方式,可以获得其乘积整体等于或小于中值的数。

$Code$

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const ll INF = 1e18;

int n, k;
int main(void){
    cin >> n >> k;
    vector<int> a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    ll l = 0, r = INF + 1;
    while(r - l > 1){
        ll mid = (l + r) / 2;
        ll cnt = 0;
        for (int i = 0; i < n; ++i)
        {
            //ai * bj <= mid  bj <= mid / ai
            auto it = upper_bound(b.begin(), b.end(), mid / a[i]);
            //在b,k / ai中加数量小于
            cnt += it - b.begin();
        }
        if(cnt < k){
            l = mid;
        }else{
            r = mid;
        }
    }

    for (ll pos = l; pos <= r; ++pos)
    {
        ll cnt = 0;
        for (int i = 0; i < n; ++i)
        {
            //ai * bj <= mid  bj <= mid / ai
            auto it = upper_bound(b.begin(), b.end(), pos / a[i]);
            //在b,k / ai中加数量小于
            cnt += it - b.begin();
        }
        if(k <= cnt){
            printf("%lld\n", pos);
            return 0;
        }
    }
}

本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

题解 CF45E 【Director】 上一篇
题解 AT2026 【天下一魔力発電】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。