二分练习之——洛谷P1182 数列分段 Section II、P1316 丢瓶盖

系统管理员 2023-06-24 08:14 19阅读 0赞

# 二分练习之——洛谷P1182 数列分段 Section II、P1316 丢瓶盖 #

做了这两道题，发现我的二分还差点火候，这完全想不到啊  
这也类似于一个二分题的模板，主要就是在于**二分搜索范围**和**check函数**

--------------------

## [一、P1182数列分段][P1182] ##

--------------------

**题目大意**：n个数组成的数列，要求分成m组，但是要求**各组的和的最大值最小**

回到所说的两个核心问题：二分搜索范围和check函数  
一、二分搜索范围怎么找呢：数列最大值和数列的和之间（答案在这范围内产生很明显）  
二、然后就是check函数：判断a数组中，每组的和是否小于x，如果小于，则：返回false，否则返回true

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<queue>
    #include<map>
    #include<stack>
    #define INF 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const int maxn=1e5;
    int a[maxn+10];
    int n,m;     //n个数分为m段
    int l,r,mid;      //l表示数列最大数，r表示数列的和,二分搜索范围产生
    int total,num;
    //判断a数组中，每组的和是否小于x，
    //如果小于，则：返回false，否则返回true
    bool check(int x){
        
        for(int i=1;i<=n;i++){
        
            if(total+a[i]<=x){
        
                total+=a[i];
            }
            else{
        
                total=a[i];
                num++;
            }
        }
        if(num>=m){
        
            return true;
        }
        else{
        
            return false;
        }
    }
    int main(){
        
        cin>>n>>m;
        l=0,r=0;
        for(int i=1;i<=n;i++){
        
            cin>>a[i];
            if(i==1){
        
                l=a[i];
            }
            else{
        
                l=max(l,a[i]);
            }
            r+=a[i];
        }
    
        //二分
        while(l<=r){
        
            total=0,num=0;
            mid=(l+r)/2;
            if(check(mid)){
        
                l=mid+1;
            }
            else{
        
                r=mid-1;
            }
        }
        cout<<l<<endl;
    }

--------------------

## [二、P1316丢瓶盖][P1316] ##

--------------------

题目大意：从n个瓶盖中找出m个，要求：距离最近的两个距离要最大

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<map>
    #include<queue>
    #include<vector>
    #define ll long long
    #define INF 0x3f3f3f3f
    #define pi cos(-1.0)
    using namespace std;
    const int maxn=1e5;
    const ll mod=100003;
    int n,m,a[maxn+10],l,r,mid;
    bool check(int x){
        
        int total=1;
        int num=1;
        for(int i=2;i<=n;i++){
        
            if(a[i]-a[num]>=x){
        
                total++;
                num=i;
            }
        }
        if(total>=m){
        
            return true;
        }
        else{
        
            return false;
        }
    }
    int main()
    {
        
        cin>>n>>m;
        for(int i=1;i<=n;i++)
           cin>>a[i];
        sort(a+1,a+n+1);
        l=1,r=a[n]-a[1];
        while(l<=r){
        
            mid=(l+r)/2;
            if(check(mid)){
        
                l=mid+1;
            }
            else{
        
                r=mid-1;
            }
        }
        //getchar();
        cout<<l-1<<endl;
        //getchar();
        return 0;
    }

[P1182]: https://www.luogu.com.cn/problem/P1182
[P1316]: https://www.luogu.com.cn/problem/P1316