2018-02-28

二分和三分

希望能整理出二分和三分的模板

整数的二分

题目

Uva

题意

有n件物品，每件物品有四个参数type, name, price, quality
每一个type中挑选一个物品，并且所有type的price之和不能超过预算b。
满足上述条件的基础之上，似的quality最大。

题解

二分quality

AC代码

#include <bits/stdc++.h>
using namespace std;
int cnt;
map<string, int> id;
int ID(string name){
    if(!id.count(name)) return id[name] = cnt++;
    return id[name];
}
const int maxn = 1e3+10;
struct Node{
    int quality;
    int price;
};
int n, b;
vector<Node> comp[maxn];
bool ok(int q){
    int sum = 0;
    for(int i=0; i<cnt; i++){
        int sz = comp[i].size();
        int price = b+1;
        for(int j=0; j<sz; j++){
            if(comp[i][j].quality>=q){
                price = min(price, comp[i][j].price);
            }
        }
        if(price == b+1) return false;
        sum+=price;
        if(sum>b) return false;
    }
    return true;
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &b);
        cnt = 0;
        for(int i=0; i<maxn; i++) comp[i].clear();
        id.clear();
        int maxq;
        for(int i=0; i<n; i++){
            char name[30], type[30];
            int price, quality;
            scanf("%s%s%d%d", type, name, &price, &quality);
            maxq = max(maxq, quality);
            comp[ID(type)].push_back((Node){quality, price});
        }
        int L = 0, R = maxq;
        while(L<R){
            int M = L + (R-L+1)/2;
            if(ok(M))L = M;
            else R = M-1;
        }
        printf("%d\n", L);
    }
    return 0;
}

小数的二分

题目

题意

n个蛋糕， f个朋友
将n个蛋糕分成f+1份，每份不能拼凑。
问每个人分得最大的蛋糕的面积

题解

二分面积即可

AC代码

一开始吧PI定义为float WA成傻逼。

#include <bits/stdc++.h>
using namespace std;
int n, f;
const int maxn = 1e4+10;
int number[maxn];
double area[maxn];
const double PI = acos(-1.0);
bool ok(double s){
    int sum = 0;
    for(int i=0; i<n; i++){
        sum += floor(area[i]/s);
    }
    if(sum>=f+1) return true;
    else return false;
}
int main()
{
    int T;
    scanf("%d", &T);
    //freopen("data.out","w",stdout);
    while(T--){
        scanf("%d%d", &n, &f);
        double max_area = -1;
        for(int i=0; i<n; i++){
            scanf("%d", &number[i]);
            area[i] = number[i]*number[i]*PI;
            max_area = max(max_area, area[i]);
        }
        double L=0, R = max_area;
        while(R-L>1e-7){
            double M = (R+L)/2.0;
            if(ok(M))L = M;
            else R = M;
        }
        printf("%.4lf\n", L);
    }
    return 0;
}

三分求峰值函数的极值或者整数的值

未解决的问题

本文标题:二分和三分

文章作者:Babydragon

发布时间:2018-02-28, 10:18:27

最后更新:2018-03-23, 13:32:49

原始链接:http://baolintian.github.io/2018/02/28/二分和三分/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。