二分法

二分模板:查找

给定n个数,然后询问m次,找个数在不在这个递增数列里,在就返回这个值,不在就返回-1.
测试样例:
5
2 5 6 9 10
4 
9 6 4 10
#include <iostream>
using namespace std;
const int N = 1e4 + 9;
int a[N], n, m;
int binary_search(int x){
    int l = 0, r = n-1;
    while(l<=r){
        int mid = (l+r)>>1;
        if(a[mid] == x){
            return mid;
        }
        if(a[mid]<x){
            l = mid + 1;
        }else {
            r = mid - 1;
        }
    }
    return -1;
}
int main() {
    cin>>n;
    for(int i = 0;i < n;++i){
        cin>>a[i];
    }
    cin>>m;
    while(m--){
        int x;
        cin>>x;
        cout<< binary_search(x)<<endl;
    }
    return 0;
}

二分法在计算机中的应用

求根号下K的值

get_sqrt(k)
    l = 0, r = k
    while r - l > eps
        mid = (l + r) / 2
        if mid * mid <= k
            l = mid
        else
            r = mid
    return l

求方程的近似解

对于方程 x4 + 5 x 3 + 6 x 2 + 7 * x + 4 = y 接受一个参数y ,求[0,100]范围之内的解,并返回,要求精确三位小数,如果没有解,返回-1。

关键点,很明显是单调递增函数,可以用二分法。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps = 1e-3;
double f(double x) {
    return pow(x, 4) + 5 * pow(x, 3) + 6 * pow(x, 2) + 7 * x + 4;
}
double cal(double y){
    if(f(0)>y || f(100)<y)
    {
        return -1;
    }
    double l = 0,r = 100;
    while(r - l > eps){
        double mid = ( l + r ) / 2;
        if(f(mid) > y){
            r = mid;
        } else {
            l = mid;
        }
    }
    return l;
}
int main () {
       double y;
    cin>>y;
    printf("%.3lf\n",cal(y));
    return 0;
}

二分快速幂

每次要写二分快速幂模板的时候,想原理,关键点是二进制,和a2x = a2x-1 * a2x-1

int Pow_mod(int a, int b, int mod){
    int res = 1, temp = a;
    for (; b; b /= 2) {
        if (b & 1) {
            res = res * temp % mod; // 2 进制上这一位为 1,乘上这一位权值
        }
        temp = temp * temp % mod; // 位数加 1,权值平方
    }
    return res;
}
#include <iostream>
using namespace std;
int pw1 (int x, int y, int p){    //递归快速幂
    if(!y){
        return 1;
    }
    int res = pw1(x,y/2,p);
    res = res*res%p;
    if(y&1){
        res = res*x%p;
    }
    return res;
}
int pw2 (int x, int y, int p){    //循环快速幂
    int res = 1;
    while(y){
        if(y&1){
            res = res*x%p;
        }
        y>>=1;
        x = x*x%p;
    }
    return res;
}
int main() {
    int x, y, p;
    cin >> x >> y >> p;
    cout << pw1(x,y,p) << endl;
    cout << pw2(x,y,p) << endl;
    return 0;
}

二分答案

8 4 
1 3 4 7 1 4 3 8
一共有m个数,最多分为k组,其和为gi,对于每组数的总和的最大值最小可以是多少?

二分需要注意一点的是在于考虑边界

#include <iostream>
using namespace std;
const int N = 1e3 + 9;
const int inf = 0x3f3f3f3f;
int n, k, a[N];
bool check(int x){
    int now = 0 ,cnt = 0;
    for(int i = 0; i < n; ++i){
        if(now + a[i] > x){
            ++cnt ;
            now = a[i];
        } else {
            now += a[i];
        }
    }
    return cnt <= k;
}
int cal(int l, int r){
    while(l < r){
        int mid  = (l + r) >> 1;
        if(check(mid)){
            r = mid ;
        } else {
            l = mid + 1;
        }
    }
    return l;
}
int main() {
    int ma = -inf , sum = 0;
    cin >> n >> k;
    for(int i = 0; i < n ; ++i){
        cin >> a[i];
        ma = max(ma,a[i]);
        sum += a[i];
    }
    cout << cal(ma, sum) << endl;
    return 0;
}
Last modification:September 18th, 2019 at 10:38 pm
如果觉得我的文章对你有用,请随意赞赏