算法竞赛进阶指南-0x04基本算法-二分

最佳牛围栏

题意:
给定一个正整数序列,求一个平均数最大的,长度不小于 L 的连续子段。

Solution:
二分答案,把数列中每个数都减去二分的值,判断是否存在一个长度不小于 L 的子段,子段和非负。

其中,求一个子段,它的和最大,字段长度不小于 L,可以转化为前缀和的形式,维护最小的前缀,这样可以找到最大的子段。

Code:

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const double eps = 1e-5;

int n, f;
double a[N], sum[N];

int main(){
    cin >> n >> f;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    double l = 0, r = 2000;
    while(r - l > eps){
        double mid = (l + r) / 2;
        for(int i = 1; i <= n; i ++)    sum[i] = sum[i - 1] + a[i] - mid;
        double ans = -1e9;
        double mi = 1e9;
        for(int i = f; i <= n; i ++){
            mi = min(mi, sum[i - f]);
            ans = max(ans, sum[i] - mi);
        }
        if(ans >= 0)    l = mid;
        else    r = mid;
    }
    cout << (int)(r * 1000) << endl;
    return 0;
}

特殊排序

题意:
蓝色 P31

Solution:
二分插入

Code:

// 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> v;
        for(int i = 1; i <= N; i ++){
            int l = 0, r = v.size();
            while(l < r){
                int mid = l + r >> 1;
                if(compare(v[mid], i)) l = mid + 1;
                else    r = mid;
            }
            v.insert(v.begin() + l, i);
        }
        return v;
    }
};

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注