借書【二分】

• 2020 年 7 月 5 日
• 筆記

借書【二分】

題目描述

DilhaoDilhao一共有nn本教科書，每本教科書都有一個難度值，他每次出題的時候都會從其中挑兩本教科書作為借鑒，如果這兩本書的難度相差越大，DilhaoDilhao出的題就會越複雜，也就是說，一道題的複雜程度等於兩本書難度差的絕對值。

這次輪到ldxxxldxxx出題啦，他想要管DilhaoDilhao借mm本書作為參考去出題，DilhaoDilhao想知道，如果ldxxxldxxx在DilhaoDilhao給出的mm本書里挑選難度相差最小的兩本書出題，那麼ldxxxldxxx出的題複雜程度最大是多少？

輸入格式

第一行是nn和mm。

接下來的nn行，每行一個整數aiai表示第ii本書的難度。

輸入格式

一個整數為ldxxxldxxx出的題複雜程度的最大值。

輸入樣例

6 3

5

7

1

17

13

10

輸出樣例

7

樣例解釋

DilhaoDilhao給了ldxxxldxxx難度為1,10,171,10,17的三本書，ldxxxldxxx挑選難度為1010和1717的兩本書，出題複雜度為77；

如果DilhaoDilhao給出其他任何三本書，其中的兩本書難度差的最小值都小於77，所以ldxxxldxxx出題最大的複雜程度為77。

數據說明

對於 30%30%的數據： 2≤n≤202≤n≤20；

對於 60%60%的數據： 2≤n≤10002≤n≤1000；

對於 100%100%的數據： 2≤n≤1000002≤n≤100000， 2≤m≤n2≤m≤n， 0≤ai≤10000000000≤ai≤1000000000。

思路分析

• 題目很好理解，一堆書中給你m本書，選出這m本書中兩本書難度差最小的值作為出題的複雜程度，最後輸出最大複雜程度，顯然是一道最小值最大化的問題，就需要用到二分

二分從哪裡入手

• 首先可以明確的是這題要對差值處理，考慮到我們要選m本中的最小差值，那麼我們完全可以將原數組排序後處理為差分數組，然後兩個數的差值從前往後加即可
• 二分過程:
  • 最大的最小差值為邊界，然後判斷右邊界（顯然右邊界最大）是否成立，成立即為最優答案，否則再判斷mid，進行區間縮小
  • 判斷條件：我們只需要看以該值作為最小差值是否能選出m個數即可（即m-1個差值）

代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int maxn=1e5+5;
int n,m,a[maxn],cf[maxn];
int Max=0;
void Init(){
	n = read(),m = read();   
    for(int i=1;i<=n;i++){
        a[i] = read();
        Max=max(Max,a[i]);
    }
    sort(a+1,a+n+1);
    for(int i=1;i<n;i++){
        cf[i]=a[i+1]-a[i];//cf差分數組
    }
}
bool check(int x){ //x為二分過程中枚舉的差值
    int cnt=0,ch=0;//ch當前的最大差值
    for(int i=1;i<n;i++){
        ch+=cf[i];
        if(ch>=x){//找到一對差值大於x
            cnt++,ch=0;//從下個位置找下一對
        }
    }
    if(cnt>=m-1)return true; //能夠找出m-1個差值
    return false;
}
int main(){
    n = read(),m = read();   
    for(int i=1;i<=n;i++){
        a[i] = read();
        Max=max(Max,a[i]);
    }
    sort(a+1,a+n+1);
    for(int i=1;i<n;i++){
        cf[i]=a[i+1]-a[i];//cf差分數組
    }
    int l=0,r=Max;
	while(l<=r){
        if(r-l==1){ //區間不能再縮小
            if(check(r)==true) //右邊界最大，判斷是否可以作為答案
                l=r;
            break;
        }
        int mid=(l+r)/2;
        if(check(mid)==true) //向右縮小空間，繼續尋找更優解
            l=mid;
        else r=mid; //中間值太大，向右縮小區間
    }
    printf("%d\n",l);//左邊界最小，一定符合答案
    return 0;
}

發量成功減1%