POJ 3232 Accelerator

二分
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 
 6 #define LL long long int
 7 
 8 using namespace std;
 9 
10 const int MAXN = 100010;
11 
12 LL a[MAXN];
13 LL M, K;
14 int N;
15 
16 bool check( LL mid )
17 {
18     LL TotUse = mid * M;
19     LL use = 0;
20     for ( int i = 0; i < N; ++i )
21     {
22         if ( a[i] <= mid ) continue;
23         if ( mid * K < a[i] ) return false;
24 
25         LL tp = ( a[i] - mid ) / ( K - 1 );
26         if ( ( a[i] - mid ) % ( K - 1 ) ) ++tp;
27         use += tp;
28     }
29     return use <= TotUse;
30 }
31 
32 int main()
33 {
34     int T;
35    // freopen( "s.out", "w", stdout );
36     scanf( "%d", &T );
37     while ( T-- )
38     {
39         LL high = -1;
40         scanf( "%d", &N );
41         for ( int i = 0; i < N; ++i )
42         {
43             scanf( "%I64d", &a[i] );
44             high = max( high, a[i] );
45         }
46         scanf( "%I64d%I64d", &M, &K );
47         if ( K == 1 )
48         {
49             printf( "%I64d\n", high );
50             continue;
51         }
52 
53         LL l = 1, r = high;
54         LL mid;
55         while ( l < r )
56         {
57             mid = ( l + r ) >> 1;
58             if ( check( mid ) )
59             {
60                 r = mid;
61             }
62             else l = mid + 1;
63         }
64         printf( "%I64d\n", l );
65     }
66     return 0;
67 }