我还记得我当年Openjudge上的二分查找整一章都没做QwQ

果然现在要还债了

现在开始补二分查找

 

一、基本模型

二分查找适用范围为一段连续的、具有单调性的区间（所以通常把二分目标所在范围意淫成数轴区间），

这样最优解的左右两边必有一边为可行解（这样才能缩小区间找到最优解）。

所以二分前还要保证二分区间有序。

下面是二分查找基本模板

int check(int); //用于判定区间中点是否为可行解int l = 1,r = L; //初始区间左右端点while(l+1 < r){    int mid = (l+r)/2;     if(check(mid) l = mid; //其实这里的区间缩减方式需要具体情况具体修改    else r = mid-1; }

显然，缩减区间部分不是重点，最关键的是那个check函数（是不是想到了函数式编程？）

区间缩减循环时间复杂度应该是O(logN)，已经被核心思想固定下来了，因此关键在check

check用于确定当前点是否为可行解，一般返回逻辑值（不过我个人倾向只返回计算值然后在while里判断）

有几个坑点需要注意的：

1. 二分终止条件和之后的最终确定最优解需要好好想想。

PS: l < r 搭配l = mid肯定出错，因为当l r在区间上相差1时l 恒等于 mid

2. 在缩减区间的过程中务必做到完善的分类讨论

PS：我经常见到有的人是搭配l = mid+1和r = mid-1加上l <= r，这样我不知道怎么考虑最优解为mid的情况，所以我是不敢这么玩的QwQ

 

二、题目

二分目标区间为1 ~ L，目标为最小距离的最大值（也就是最优解）。这里check返回的是使x为最小距离的需要搬走的石头数

这个check有点妙

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define maxn 100000 6 using namespace std; 7  8 int L,n,m,arr[maxn]; 9 10 int check(int line){11     12     int pre = 0,ans = 0;13     14     for(int i = 1;i <= n;i++){ //关键点115         if(arr[i]-pre < line) ans++;16         else pre = arr[i];17     }18     19     return ans;20 }21 22 int main(){23     scanf("%d%d%d",&L,&n,&m);24     25     for(int i = 1;i <= n;i++) scanf("%d",&arr[i]);26     27     arr[++n] = L;28     29     sort(arr+1,arr+1+n);30     31     int l = 0,r = L;32     33     while(l+1 < r){ //关键点2，联系上面的坑点1.34         int mid = (l+r)/2;35         if(check(mid) <= m) l = mid;36         else r = mid-1;37     }38     39     if(check(r) <= m) printf("%d",r);40     else printf("%d",l);41     42     return 0;43 }
         
        
       
      

 

 二分区间为申请名单，目标为分配出现问题的那个申请者。那么怎么Check呢？每Check一个人的时候就直接从头计算一遍。虽然这听上去非常的低效但是这只是O((n+m)logn)。再加上差分数组进行优化，最后还是跑过了（可能这是正解？).至于用线段树怎么写我还无头绪。

1 #include
      
        2 #include
       
         3 #include
        
          4 #define maxn 1000000 5 #define mid (l+r)/2 6 using namespace std; 7  8 int n,m,a,b,c,arr[maxn],data[maxn][3],brr[maxn],x; 9 10 int check(int k){ //O(m+n)11     memset(brr,0,sizeof(brr));12     13     for(int i = 1;i <= k;i++){14         brr[data[i][1]] -= data[i][0];15         brr[data[i][2]+1] += data[i][0];16     }17     18     x = 0;19     20     for(int i = 1;i <= n;i++){21         x += arr[i]+brr[i];22 //        if(k == 2) printf("%d ",x); 23         if(x < 0) return 0;24     }25     26 //    cout << endl;27     28     return 1;29 }30 31 int main(){32     33     scanf("%d%d",&n,&m);34     35     for(int i = 1;i <= n;i++){36         scanf("%d",&brr[i]);37         arr[i] = brr[i] - brr[i-1];38     }39     40 //    for(int i = 1;i <= n;i++){41 //        printf("%d ",arr[i]);42 //    }43     44 //    cout << endl;45     46     47     for(int i = 1;i <= m;i++){48         scanf("%d%d%d",&data[i][0],&data[i][1],&data[i][2]);49     }50     51     int l = 1,r = m;52     while(l < r){53         if(check(mid)) l = mid+1;54         else r = mid;55     }56     57     if(!check(r)) printf("-1\n%d",r);58     else if(!check(l)) printf("-1\n%d",l);59     else printf("0");60 //    printf("B%d ",r);61 //    printf("C%d ",check(2));62     return 0;63 }
        
       
      

这道题有专门写解题报告。

 

二分目标为参数W，二分范围为矿石的质量，嗯嗯。显然的参数W影响参与计算的矿石数量，也就线性影响计算出来的检验值，因此可以二分。

思路倒是简单，但是还是被各种细节坑。QwQ

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define LL long long 6 #define INF (1LL<<62) 7 #define maxn 1000000 8 #define mid (L+R)/2 9 using namespace std;10 11 LL n,m,S,ret = INF,maxw = 0,tmp;12 LL cnt1[maxn],cnt2[maxn],w[maxn],v[maxn],ql[maxn],qr[maxn];13 14 int check(int x){15     cnt1[0] = cnt2[0] = 0;16     for(int i = 1;i <= m;i++){17         cnt1[i] = cnt1[i-1];18         cnt2[i] = cnt2[i-1];19         if(w[i] >= x){20             cnt1[i]++;21             cnt2[i] += v[i];22         }23     }24     25     LL ans = 0;26     27     for(int i = 1;i <= m;i++){28         ans += (cnt1[qr[i]]-cnt1[ql[i]-1])*(cnt2[qr[i]]-cnt2[ql[i]-1]);29     }30     31     return ans;32 }33 34 int main(){35     scanf("%lld%lld%lld",&n,&m,&S);36     37     for(int i = 1;i <= n;i++){38         scanf("%lld%lld",&w[i],&v[i]);39         maxw = maxw>w[i]?maxw:w[i];40     }41     42     for(int i = 1;i <= m;i++){43         scanf("%lld%lld",&ql[i],&qr[i]);44     }45     46     int L = 0,R = maxw+1;47     48     while(L <= R){49         tmp = check(mid);50         ret = abs(S-tmp)
          
           = S) L = mid+1;52         else R = mid-1;53     }54     55     printf("%lld",ret);56     57     return 0;58 }59 60 推荐不看
          
         
        
       
      

这道题有专门写解题报告。