008二分答案+贪心判断——算法备赛

二分答案+贪心判断

有些问题，从已知信息推出答案，细节太多，过程繁杂，不易解答。
从猜答案出发，贪心地判断该答案是否合法是个不错的思路，这要求所有可能的答案是单调的（例：x满足条件，大于x的数肯定满足条件），以便使用二分快速查找到题目要求的最优答案。

在二分答案时，最后答案该取 l 还是 r？中间缩小范围时，是l=mid+1还是l=mid是r=mid-1还是r=mid？

受《算法导论》一书启发，应该寻找循环不变量，所谓循环不变量，通俗一点解释就是在循环过程中包含的代表意义始终不变（作者的理解）。

例如初始的答案集是[L,R],R初始时是满足条件的已知最大值，L是答案的下界（可以推断答案不会小于L），当check(mid)(贪心判断函数)为true时，说明mid是满足条件的，那[mid,R]都满足条件，为保持R代表的含义（满足条件的已知最大值）始终不变，应该将R赋值为mid而不是mid-1，反之check(mid)(贪心判断函数)为false时，为保持L代表的含义（答案的下界）始终不变，应该将L赋值为mid+1而不是mid，最后L==R时的R就是最优所求的答案。

分组游戏

题目描述

思路

二分法+贪心

二分猜数，贪心分组。

首先对n个同学的身高数组排序，最大极差肯定在 [0,H [n-1] - H [0] ] 范围内

通过二分查找到这个最大极差的最小值。每次二分时取得一个maxn，利用贪心，使每组极差 x<=maxn的情况下分组,共取得cnt组，若cnt<=k说明maxn偏大，cnt>k说明maxn偏小，不断二分直到（l==r）取得最后答案。

原题链接

代码

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool check(vector<int>&dat,int k,int maxn){int cnt=1,d=dat[0];for(int i=1;i<dat.size();i++){if(dat[i]-d>maxn){  //极差大于maxn另起一组cnt++; d=dat[i];}}return cnt<=k;
}
int main()
{// 请在此输入您的代码int n,m;cin>>n>>m;vector<int>dat(n);for(int i=0;i<n;i++){cin>>dat[i];}sort(dat.begin(),dat.end());int l=0,r=dat[n-1]-dat[0];while(l<r){int mid=l+(r-l)/2;if(check(dat,m,mid)) r=mid;else l=mid+1;}cout<<l;return 0;
}

H指数

问题描述

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。

请你设计并实现对数时间复杂度的算法解决此问题。

原题链接

思路分析

因为 citations 已经按照 升序排列 ，

当citatios[i]>=i, citatios[i]~citatios[n-1]都 >= i 则有n-i篇论文引用次数大于等于i ;

当citatios[i]<i, citatios[0]~citatios[i]都 < i 。

采用二分查找 在区间 [1,n]中询问有多少（x）篇论文引用次数大于等于x。

int hIndex(vector<int> &citations) {// 在区间 [left, right] 内询问int n = citations.size();int left = 1;int right = n;while (left <= right) { // 区间不为空  当left==right时还要再询问一次。// 循环不变量：// left-1 的回答一定为「是」// right+1 的回答一定为「否」int mid = (left + right) / 2; // left+(right-left)/2// 引用次数最多的 mid 篇论文，引用次数均 >= midif (citations[n - mid] >= mid) {left = mid + 1; // 询问范围向右缩小到 [mid+1, right]} else {right = mid - 1; // 询问范围缩小到 [left, mid-1]}}// 循环结束后 right 等于 left-1，回答一定为「是」// 根据循环不变量，right 现在是最大的回答为「是」的数return right;}
};

分割正方形|

问题描述

给你一个二维整数数组 squares ，其中 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。

找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积 等于 该线以下正方形的总面积。

答案如果与实际答案的误差在 10-5 以内，将视为正确答案。

注意：正方形 可能会 重叠。重叠区域应该被 多次计数 。

原题链接

代码

double separateSquares(vector<vector<int>>& squares) {double tot_area = 0.;int max_y = 0;for (auto& sq : squares) {tot_area += 1LL * sq[2] * sq[2];max_y = max(max_y, sq[1] + sq[2]);}const int M = 100'000; // 也可以调大一些，避免累计误差auto check = [&](long long multi_y) -> bool {double y = 1.0 * multi_y / M;double area = 0.;for (auto& sq : squares) {if (sq[1] < y) {double l = sq[2];area += l * min(y - sq[1], l);}}return area >= tot_area / 2;};long long left = 0, right = 1LL * max_y * M;  //转化为整数二分，分割线right/M以下面积和>=总面积和一半while (left + 1 < right) {long long mid = left + (right - left) / 2;(check(mid) ? right : left) = mid;}return 1.0 * right / M;  //最小的符合要求的答案}
/*
记 M=10^5，可以改为二分整数 y⋅M，最后答案再除以M。在使用整数计算的前提下，这可以保证二分结束时的答案与正确答案的绝对误差严格小于 10^−5。
*/

• 时间复杂度：O(nlog(MU))，其中 n 是 squares 的长度，M=10^5，U=max(yi+li)。