Home 二分
Post
Cancel

二分

带领只会基础二分的「真正的蒟蒻」 (例如, 我) 进入一个二分新境界

AcWing 102 最佳牛围栏

Link

这道题的二分用在了找平均值上. 首先这个平均值并不是题目数据给出来的, 因此不能像别的二分题那样对数组索引进行二分; 况且, 这道题根本不用也不能对数组进行从大到小排序. 这道题的二分是在 n 块地中牛的数量上进行二分, 并且是用浮点数进行计算, 注意自定义精度判断.

二分的 low 初始化为 0, high 初始化为 n 块地中牛数的最大值. 每次计算 mid=(high+low)/2, 这个 mid 就是当前我们假设的平均值.

针对当前这个平均值, 接下来的任务就是在原序列中寻找有没有一个连续的、长度大于等于 f 的子序列的平均值不小于 mid. 别忘了我们本来是要找长度不少于 f 的子序列的平均值最大值的, 但是如果我们能够找到长度大于等于 f 且平均值不小于 mid 的子序列, 那就说明平均值还有继续增大的空间; 如果我们找到的是长度大于等于 f 且平均值等于 mid 的子序列, 那么就说明这个可以作为答案, 但是仍然需要增大平均值看看有没有更大的可能.

因此, 如果 mid 小于等于当前区间的平均值, 那么就看看有没有更大的平均值, 即让 low=mid; 否则, 就说明这个 mid 实际上是达不到的, 那就让 r=mid, 看看比它小的可不可行.

那么问题来了, 指定了一个数 mid 作为平均数, 我们怎么找到平均数大于等于它的一段区间?

对于一段区间, 我们可以用区间内的每个数减去当前指定的这个平均数, 如果减去后的区间和大于 0, 就说明原来的区间平均数大于 mid; 如果小于 0, 则原来的区间平均数小于 mid. 这里的区间和就可以使用前缀和来搞定.

用前缀和固然简单, 但是查找的时候必然要用到两层 for 循环. 这里就可以用双重指针来优化一下. 设 i=0,j=f, 每次使两个数 +1, 这就使得 i,j 始终满足相距 f 的距离. 用 minv 来存储 i 所遍历到的前缀和的最小值, 这样我们比较的距离就一定是 >=f 的 (因为 i 遍历到最小值的地方可能是小于当前 i 的, 而当前的 j 等于当前的 i 加上 f). 此时用 j 处的前缀和减去 minv 就能得到长度大于等于 f 的区间的平均值的当前最大值了, 一旦这个当前最大值 >=0 就说明这个 mid 是可行的, 接下来就是去看看有没有更大的 mid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
const double EPSILON=1e-5;
int n,f,cows[100010];
double sum[100010];
bool check(double mid){
    for(int i=1;i<=n;++i)
        sum[i]=sum[i-1]+cows[i]-mid;
    double minv=0;
    for(int i=0,j=f;j<=n;++i,++j){
        minv=min(minv,sum[i]);
        if(sum[j]-minv>=0) return true;
    }
    return false;
}
int main() {
    scanf("%d%d",&n,&f);
    double low=0,high=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&cows[i]);
        high=max(high,(double)cows[i]);
    }
    while(high-low>EPSILON){ //因为是实数所以要用精度
        double mid=(low+high)/2; //不是>>1 这里是实数
        if(check(mid)) low=mid;
        else high=mid;
    }
    printf("%d\n",(int)(high*1000)); //因为找的极大值 所以要右端点*1000 否则可能会出错
    return 0;
}

AcWing 113 特殊排序

Link

不知道 忘了 什么是反对称?

  • 若 (a,b) 属于 R, 则 (b,a) 属于 R, 称 R 是对称的;
  • 若 (a,b) 属于 R, 但 (b,a) 不属于 R, 称 R 是反对称的.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int>ans;
        ans.push_back(1);
        for(int i=2;i<=N;++i){
            int l=0,r=ans.size()-1; //l是ans第一个元素的下标,r是ans最后一个元素的下标
            while(l<=r){
                int mid=(l+r)>>1;
                if(compare(ans[mid],i)) l=mid+1;
                else r=mid-1;
            }
            ans.push_back(i);
            for(int j=ans.size()-1;j>l;--j)
                swap(ans[j],ans[j-1]);
        }
        return ans;
    }
};
This post is licensed under CC BY 4.0 by the author.