首页 > 其他分享 >【牛客小白72】E 二分答案

【牛客小白72】E 二分答案

时间:2023-05-13 18:11:53浏览次数:59  
标签:二分 10 int res ll mid 牛客 72

https://ac.nowcoder.com/acm/contest/56825/E

题意

给你 \(10^{10}\) 个数(数组a n 个数,数组b m 个数,数是 a*b 的集合),有 \(Q\) (Q为常数)个询问,每次问你第 \(x\) 小的数是多少

思路

最暴力的思路肯定是把所有数放在一起,然后排序。易知时间复杂度为 \(nlogn(n = 1e10)\),会超时。

继续思考,如果给你一个数字,求它在 1e10 个数中的次序,可以在 On(双指针) / Onlogn(二分查找) 时间内解决。如果这个数字的次序大于x(第[>x]小),说明比答案偏大,让r=mid-1;反之让l=mid+1,然后就可以二分出答案啦。

时间复杂度 O(n * log2(n * m))

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
ll n, m, k, q, x;
ll a[N], b[N];
struct node{
    int x, y;
}c[N * 10];
vector<ll> v;

ll Count(ll mid) {
    ll res = 0;   // mid是第几小 res个小于mid的
    int ind = m;
    for(int i = 1; i <= n; i++) {
        while(a[i] * b[ind] >= mid) ind--;
        res += ind;
    }
    for(auto i : v) {
        if(i < mid) res--;
    }
    // cout << "mid: " << mid << " rank: " << res + 1  << endl;  ////
    return res + 1;
}

int main() {
    cin >> n >> m >> k >> q;
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for(int i = 1; i <= m; i++) scanf("%lld", &b[i]); 
    for(int i = 1; i <= k; i++) {
        scanf("%d%d", &c[i].x, &c[i].y);
        v.push_back(a[c[i].x] * b[c[i].y]);
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    while(q--) {
        cin >> x;
        ll l = 1, r = 1e18, mid, ans = -1;
        while(l <= r) {
            mid = (l + r) >> 1;
            if(Count(mid) <= x) ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        printf("%lld\n", ans);
    }
    return 0; 
}

标签:二分,10,int,res,ll,mid,牛客,72
From: https://www.cnblogs.com/re0acm/p/17397841.html

相关文章

  • day72(2023.5.13)
    1.Servlet技术详解 2.创建第一个Servlet案例 3.Tomcat运行过程 4.Servlet的生命周期 5.Servlet处理请求的原理 6.Servlet的作用 7.在Idea中创建Web工程 在Idea创建Web工程添加servlet-api.jar 在Idea中配置To......
  • 西门子S7200smartPLC与三菱FX3uPlc做485Modbus RTU通信,西门子S7200smartPLC做主站轮训
    西门子S7200smartPLC与三菱FX3uPlc做485ModbusRTU通信,西门子S7200smartPLC做主站轮训扫描读取写去数据转入三菱Plc!通信已测试没有问题,YID:3135622398098741......
  • 【二分查找】LeetCode 74. 搜索二维矩阵思路
    题目链接74.搜索二维矩阵思路思路因为矩阵中每行都按升序排列,且每行的第一个整数大于前一行的最后一个整数。所以整个矩阵其实就是一个大的升序的一维数组,可以使用二分查找的方法对“一维数组”进行搜索,只不过在获取元素的过程中需要进行一步一维索引到二维索引的映射。代码......
  • 【二分查找】LeetCode 162. 寻找峰值思路
    题目链接162.寻找峰值思路思路一个不严谨但是好理解的思路是:如果\(nums[mid]>nums[mid+1]\),那么\(nums[mid+1]\)肯定不是峰值,此时让\(right=mid\),从左边继续找峰值。反之则\(nums[mid]\)肯定不为峰值,让\(left=mid+1\)。代码classSolution{public......
  • 【数组01】二分查找&移除元素
    TableofContents二分查找704.二分查找35.搜索插入位置34.在排序数组中查找元素的第一个和最后一个位置69.x的平方根367.有效完全平方数移除元素27.移除元素26.删除排序数组中的重复项283.移动零844.比较含退格的字符串977.有序数组的平方Solutions7......
  • 【二分查找】LeetCode 278. 第一个错误的版本
    题目链接278.第一个错误的版本思路二分查找代码publicclassSolutionextendsVersionControl{publicintfirstBadVersion(intn){intleft=1,right=n-1;while(left<=right){intmid=left+(right-left)/2;......
  • Codeforces Round 872 (Div. 2)
    CodeforcesRound872(Div.2)感谢灵茶山艾府A(脑筋急转弯)给一个回文字符串,找出最长的不回文子串。子串可以是不连续的。没有则输出-1;如果全都是一个字母,那就是-1否则是n-1。因为在原来回文的基础上总可以去掉一个使得不回文(前提是不是全部都是一个字母)B(贪心)给出n*m个数,......
  • 小白月赛72
    给定一个正整数�n,求[1,�][1,n]中因子数量为奇数的正整数的个数。第一行包含一个正整数TTT (1≤T≤103)(1\leqT\leq10^3)(1≤T≤103),表示数据组数。每组数据只有一行,包含一个正整数nnn (1≤n≤4×103)(1\leqn\leq4\times10^{3})(1≤n≤4×103)输出�T行,第�i行表示第�i次询问......
  • Qt编写视频监控系统72-通过onvif增删改查OSD
    一、前言之前监控系统中原创的onvif协议解析机制,已经能够满足绝大部分用户的需要,比如搜索设备、获取视频流地址并播放、云台控制、预置位管理、图片亮度色彩饱和度等参数设置等,近期又多了一个需求,那就是通过onvif国际标准协议来对摄像头的OSD进行增删改查,可以通过协议添加OSD、删......
  • 2023五一杯B题问题四----基于二分最大流最优解
    4.1问题四的分析:本题要求建立一个最小成本的运输策略,考虑最大网络流问题(MaximumFlowProblem),对于一个带权有向图G(V,E),其中V为图中所有点的集合,E为所有边的集合,且每一条边都有它的流量上限.这个带权有向图中有两个特殊的点:源(source)节点s和汇(sink)节点t,且这两个点......