poj 3232 Accelerator

http://poj.org/problem?id=3232

题意：有一个含有n辆车的车队，当前距离终点的距离已知，有m个加速器，每个加速器在一个时刻只能给一辆车用，一旦使用就会使得其速度由1变成k，加速器可以重复使用，问最快所有车辆到达终点的时间。

思路：二分枚举所需的最短时间。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 300000
 5 #define ll long long
 6 using namespace std;
 7 
 8 ll t,n,m,k;
 9 ll a[maxn];
10 
11 bool ok(ll c)
12 {
13     ll cnt=0,x=c*m;
14     for(int i=0; i<n; i++)
15     {
16         if(a[i]<=c) continue;
17         if((a[i]-c)%(k-1)==0)
18         cnt=((a[i]-c)/(k-1));
19         else
20         cnt=((a[i]-c)/(k-1))+1;
21         if(cnt>c) return false;
22         x-=cnt;
23         if(x<0) return false;
24     }
25     return true;
26 }
27 
28 
29 int main()
30 {
31     scanf("%lld",&t);
32     while(t--)
33     {
34         scanf("%lld",&n);
35         ll max1=0;
36         for(int i=0; i<n; i++)
37         {
38             scanf("%lld",&a[i]);
39             max1=max(max1,a[i]);
40         }
41         scanf("%lld%lld",&m,&k);
42         ll l=0,r=max1;
43         if(k==1)
44         {
45             printf("%lld
",max1);
46             continue;
47         }
48         int mid;
49         while(l<r)
50         {
51             mid=(l+r)>>1;
52             if(ok(mid))
53             {
54                 r=mid;
55             }
56             else l=mid+1;
57         }
58         printf("%lld
",l);
59     }
60     return 0;
61 }

View Code