CQUPT 集训队专题训练（二分/三分）

二分 三分

题目链接

A - Strange fuction

题意

F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100)
给你y,找F(x)的最小值

思路

依专题有：本题思路为二分
由于F'(x)单调递增
又F'(x) > F'(0) = -y
所以F(x)可以先减后增
所以需要在0<=x<=100这个区间查找零点(F(x)在零点处取得最小值)
二分查找零点即可

AC代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;

double F(double x,double y){
    return 6*pow(x,7)+8*pow(x,6)+7*pow(x,3)+5*x*x-y*x;
}

double F1(double x,double y){
    return 42*pow(x,6)+48*pow(x,5)+21*x*x+10*x-y;
}

int main(){
    double x1,x2,y,ans;
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%lf",&y);
        x1 = 0.0;x2 = 100.0;
        ans = (x1+x2)/2.0;
        while( x2-x1 >= 0.000001 ){
            if( F1(ans,y) > 0 )
                x2 = ans;
            else
                x1 = ans;
            ans = (x1+x2)/2.0;
        }
        printf("%.4lf\n",F(ans,y));
    }
    return 0;
} 

B - Can you find it?

题意

对于给定的3个序列
然后求一个值是否满足
这个值能在各个序列中找到一个值，使得相加等于这个值

思路

一个二分三重暴力n^3log n---T了
所以需要合并一个n进入log，将复杂度下降n^2log n^2
所以将两个数组合并后
先枚举未合并的数组 o(n)
再二分枚举合并数组 o(log n^2)

AC代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define N 505
int l[N],m[N],n[N],s[2*N];
int lm[N*N];
int a,b,c,ssR,d;

void landn(){
    d = 0;
    for(int i = 0 ; i < a ; i++){
        for(int k = 0 ; k < b ; k++){
            if(l[i]+m[k] == lm[d-1])    continue;
            lm[d++] = l[i] + m[k];
        }
    }
    sort(lm,lm+d);
}

bool find(int y){
    for( int i = 0 ; i < c ; i++ ){
        int ans = y-n[i];
        if(ans < lm[0] )    continue;
        int mi = 0 , ma = d-1 , mid = (mi+ma)/2;
        while( mi < mid && ans != lm[mid] ){
            if( ans > lm[mid] )     mi = mid;
            else    ma = mid;
            mid = (mi+ma)/2;
        }
        if( ans == lm[mid] || ans == lm[mi] || ans == lm[ma] )  return true;
    }
    return false;
}

int main(){
    int kase = 0;
    while( scanf("%d%d%d",&a,&b,&c) != EOF &&a&&b&&c ){
        for(int i = 0 ; i < a;i++)  scanf("%d",l+i);sort(l,l+a);
        for(int i = 0 ; i < b;i++)  scanf("%d",m+i);sort(m,m+b);
        landn();
        for(int i = 0 ; i < c;i++)  scanf("%d",n+i);sort(n,n+c);
        scanf("%d",&ssR);
        for(int i = 0 ; i < ssR;i++)    scanf("%d",s+i);
        printf("Case %d:\n",++kase);
        for(int i = 0 ; i < ssR;i++){
            if( find(s[i]) )    printf("YES\n");
            else    printf("NO\n");         
        }
    }
    return 0;
}

C - Monthly Expense

题意

对于给定的序列，将其分成m段(0< m<=M)
使得每一段之和的最大值最小，并求出最小值

思路

依专题有，本题使用二分
于是二分区间为[maxn,sum]
其中maxn = 序列最大值 ， sum 为序列所有值之和
暴力出奇迹

AC代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define N 100007
int x[N],n,m,sum,maxd;

bool can(int y){
    int count = 0,now = 0;
    for(int i = 0 ; i < n ; i++){
        now += x[i];
        if(now > y){
            count++;
            now = x[i];
        }else if(now == y){
            count++;
            now = 0;
        }
    }
    if(now != 0)    count++;
    if(count <= m)  return true;
    return false;
}

int solve(){
    int mi = maxd,ma = sum,mid = (mi+ma)/2;
    if(can(mi)) return mi;
    else{
        while(ma - mi > 1){
            if(can(mid))    ma = mid;
            else mi = mid;
            mid = (mi+ma)/2;
        }
    }
    if(can(mi))     return mi;
    else return ma;
}

int main(){
    while( scanf("%d%d",&n,&m) != EOF &&n&&m ){
        sum = 0;maxd = 0;
        for(int i = 0 ; i < n ; i++){
            scanf("%d",x+i);
            sum += x[i];
            if(x[i] >= maxd)    maxd = x[i];
        }
        printf("%d\n",solve());
    }
    return 0;
}

D - River Hopscotch

题意

在一条长为L的河流里面分布着N块石头，每块石头的位置已知
N块石头不包括河流开始和河流结束两块
现在让你从N块石头中选择拿走M块石头
不能拿走河流开始与河流结束的两块石头
使得所有石头中相邻两块石头的最小距离最大
求出这个最大值

思路

依套题性质有：本题为二分题
所以有二分区间[minn,L]
其中minn表示当前相邻两块石头的最小距离
然后暴力枚举即可

AC代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define N 50007
int x[N],l,n,m;
int d[N],ma,mi;

bool can(int y){
    for(int i = 0 ; i < n ; i++)    d[i] = x[i];
    int count = 0 , dis = 0;
    for(int i = 1 ; i < n ; i++){
        if( dis + d[i] - d[i-1] < y  ){
            dis += d[i] - d[i-1];
            count++;
        }else   dis = 0;
        if(count > m)   return false;
    }
    return true;
}

int solve(){
    int mid = (mi+ma)/2;
    while(mi < mid){
        if(can(mid))    mi = mid;
        else ma = mid;
        mid = (mi+ma)/2;    
    }
    if(can(ma)) return ma;
    if(can(mid))    return mid;
    return mi;
}

int main(){
    while( scanf("%d%d%d",&l,&n,&m) != EOF ){
        x[0] = 0;
        x[n+1] = l;
        for(int i = 1 ; i <= n ; i++)   scanf("%d",x+i);sort(x+1,x+n+1);
        n += 2;ma = l;mi = l;
        for(int i = 1 , k = 0; i <= n ; i++)    if(mi > x[i] - x[i-1])  mi = x[i]-x[i-1];
        printf("%d\n",solve());
    }
    return 0;
}

E - Communication System

题意

要你从N个通信公司拉网线
每个公司都拉且只拉一条网线
每个公司都有自己的套餐(ai带宽 bi美元)
现在让你选择，使得amin/bsum最大，并求出最大值
bsum表示你选的所有套餐费用
amin表示你选的所有套餐带宽最小的那个

思路

没用二分。。。直接暴力过的。。

AC代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define N 110
struct ssR{
    int b,p;
};
struct ssR r[N][N];
int rc[N];
int n,m,top;

bool cmp(struct ssR a,struct ssR b){
    if(a.p == b.p)  return a.b > b.b;
    return a.p<b.p; 
}

double can(double a , double b , int c){
    double psum = b;
    for(int i = 0 ; i < n ; i++){
        if(i == c)  continue;
        bool f = false;
        for(int k = 0 ; k < rc[i] && !f; k++)
            if( (double)r[i][k].b >= a ){
                psum += (double)r[i][k].p;
                f = true;
            }
        if(!f)  return 0;
    }
    return psum;
}

void solve(){
    double bmin;
    double ans = 0;
    for(int i = 0; i < n;i++){
        for(int k = 0 ; k < rc[i] ; k++){
            bmin = (double)r[i][k].b;
            double pmax = can(bmin,(double)r[i][k].p,i);
            //printf("bmin = %.0lf,pmax = %.0lf,ans = %.3lf\n",bmin,pmax,ans);
            if(pmax > 0 && bmin/pmax > ans )    ans = bmin/pmax;
        }   
    } 
    printf("%.3lf\n",ans);  
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        top = 0;
        scanf("%d",&n);
        for(int i = 0 ; i < n ; i++){
            scanf("%d",rc+i);
            for(int k = 0 ; k < rc[i];k++){
                scanf("%d%d",&r[i][k].b,&r[i][k].p);
                //b[top++] = r[i][k].b;
            }   
            sort(r[i],r[i]+rc[i],cmp);
        }
        //sort(b,b+top);
        solve();
    }
    return 0;
} 

F - Light Bulb

题意

图片不会拉上来
就是根据图片求L的最大值

思路

根据复杂的推算得
L = (hD-Hx)/(D-x) + x
然后他是凸函数
所以用三分法求极值即可

AC代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
double H,h,d,ans;

double f(double x){
    return (h-x)*d/(H-x)+x;
}

void solve(){
    double mi = 0 , ma = h , mid1 = (ma-mi)/3.0+mi,mid2 = 2.0*(ma-mi)/3.0+mi;
    while( ma - mi > 1e-12 ){
        double a = f(mid1) , b = f(mid2);
        if( a > b ){
            ma = mid2;
        }else{
            mi = mid1;
        }
         mid1 = (ma-mi)/3.0+mi;mid2 = 2.0*(ma-mi)/3.0+mi;
    }
    ans = f(mid2);
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%lf%lf%lf",&H,&h,&d);
        solve();
        printf("%.3lf\n",ans);
    }
    return 0;
}