Fegla and the Bed Bugs 二分-白红宇

Fegla and the Bed Bugs 二分

阅读量：6802 次

发布时间：2019-06-26

本文共 2251 字，大约阅读时间需要 7 分钟。

Fegla and the Bed Bugs

Fegla, also known as mmaw, is coaching a lot of teams. All these teams train together in one place,

unfortunately this place doesn’t have any good ventilation and is quite small relative to the number

of teams. All these circumstances resulted in a strange creature appearing! That creature is called

The Bed Bug!

These are parasitic bugs; they feed on human blood by biting them. What was strange and confused

Fegla, is that some of the team members did not get bitten at all! However, he was more interested in

eliminating these bugs. After observing the bugs’ behavior for some time, he concluded that he

needed to stop them from reproducing to eliminate them. They reproduce by getting very close to

each other.

And so, Fegla needs your help. Given a straight line of empty cells N and the number of bugs K, tell

Fegla the best assignment for the bugs to maximize the minimum number of empty cells between

each two consecutive bugs on that line.

For example, given N=4 and K=2, the answer would be 2, according to the best assignment:

Bed Bug Empty Empty Bed Bug

Input Specification

Input will start with an integer T representing the number of test cases. Followed by T lines each line

contains two integers N, K.

You can assume that

2 <= N <= 200

2 <= K <= N

Output Specification

For each test case in a separate line, output the minimum distance between EACH two consecutive

bugs in the best assignment.

Sample Input

4 2

3 2

Sample Output

思路：很典型的二分试题，因为答案满足单调性，且有judge函数满足贪心性质。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))using namespace std ;typedef unsigned long long LL ;int N ,K ;int judge(int Len){ int id=1 ; for(int i=2;i<=K;i++) id+=(Len+1) ; return id<=N ;}int calc(){ int ans ,Left , Right ,Mid ; Left=0 ; Right=N ; while(Left<=Right){ Mid=(Left+Right)>>1 ; if(judge(Mid)){ ans=Mid ; Left=Mid+1 ; } else Right=Mid-1 ; } return ans ;}int main(){ int T ; cin>>T ; while(T--){ cin>>N>>K ; cout<
                 
                  <