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;
}