hdu-4519-二分-鄭廠長系列故事——體檢

題目大意：

有n個人體檢，每個人要檢查k個項目，有m個醫生，每個醫生檢查每個人的一個項目需要花費1分鐘，問你檢查完所有的人最少需要花費多長時間。要求：每個醫生每次只能檢查一個人的一個項目，每個人同一分鐘只能接受一個醫生檢查一個項目。

解題思路：

很容易想到二分。

每個人都有k個項目，顯然最小的時間為k分鐘，如果比k小的話，肯定存在同一分鐘有一個人檢查了超過兩個項目，不和題意。

考慮最壞的情況，只有一個醫生的話，需要花費n*k分鐘。

然後對於第一個醫生，可以這樣構造，他的mid分鐘一次檢查a11,a12,a13,,,,,a1k然後a2(k+1).....a2mid,如此類推。這樣可以把每個醫生的就診單序列給出來。當然每個人的檢查項目的數量也可以不同。

詳見代碼：

[cpp]
SPAN style="FONT-SIZE: 18px">#include<iostream> 
#include<cmath>  
#include<cstdio>  
#include<cstdlib>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<stack>  
#include<list>  
#include<queue>  
#define eps 1e-6  
#define INF (1<<30)  
#define PI acos(-1.0)  
using namespace std; 
 
int main() 
{ 
   int t,n,k,m; 
 
   scanf("%d",&t); 
   while(t--) 
   { 
      scanf("%d%d%d",&n,&k,&m); 
      int left=k,right=n*k,mid,ans; 
 
      while(left<=right) 
      { 
         mid=(left+right)/2; 
 
         if(mid*m>=n*k) //這個時間的話，可以檢查完所有的病人  
         { 
            ans=mid; 
            right=mid-1; 
         } 
         else 
            left=mid+1; 
      } 
      printf("%d\n",ans); 
   } 
 
   return 0; 
} 
 
</SPAN> 

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF (1<<30)
#define PI acos(-1.0)
using namespace std;

int main()
{
   int t,n,k,m;

   scanf("%d",&t);
   while(t--)
   {
      scanf("%d%d%d",&n,&k,&m);
      int left=k,right=n*k,mid,ans;

      while(left<=right)
      {
         mid=(left+right)/2;

         if(mid*m>=n*k) //這個時間的話，可以檢查完所有的病人
         {
            ans=mid;
            right=mid-1;
         }
         else
            left=mid+1;
      }
      printf("%d\n",ans);
   }

   return 0;
}