UVa12032

UVa12032
2分探索

view plainprint?

1. #include <iostream>  
2. #include <algorithm>  
3. #include <vector>  
4. #include <set>  
5. #include <map>  
6. #include <queue>  
7. #include <stack>  
8.   
9. #include <cstdio>  
10. #include <cstring>  
11. #include <cstdlib>  
12. #include <cmath>  
13.   
14. #define REP(i, n) for(int i=0; i<(int)n; ++i)  
15. #define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)  
16. #define ALL(c) (c).begin(),(c).end()  
17.   
18. typedef long long int lli;  
19.   
20. using namespace std;  
21.   
22. const int N = 100000 + 1;  
23. int h[N];  
24.   
25. bool sim(int k, int n)  
26. {  
27.   for (int i = 0; i + 1< n; ++i) {  
28.     int diff = h[i + 1] - h[i];  
29.     if (k < diff) return false;  
30.     k -= diff == k;  
31.   }  
32.   return true;  
33. }  
34.   
35. int main(int argc, char *argv[])  
36. {  
37.   int tc;  
38.   cin >> tc;  
39.   while (tc--) {  
40.     int n;  
41.     cin >> n;      
42.     for (int i = 0; i < n; ++i) {  
43.       cin >> h[i + 1];  
44.     }  
45.     ++n;  
46.   
47.     int s = 0;  
48.     int b = 10000000 + 1;  
49.     while (s + 1 < b) {  
50.       int c = (s + b) / 2;  
51.       if (sim(c, n)) b = c;  
52.       else s = c;  
53.     }  
54.     static int cnt = 0;  
55.     cout << "Case " << ++cnt << ": " << b << endl;  
56.   }  
57.   return 0;  
58. }  

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()

typedef long long int lli;

using namespace std;

const int N = 100000 + 1;
int h[N];

bool sim(int k, int n)
{
  for (int i = 0; i + 1< n; ++i) {
    int diff = h[i + 1] - h[i];
    if (k < diff) return false;
    k -= diff == k;
  }
  return true;
}

int main(int argc, char *argv[])
{
  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;    
    for (int i = 0; i < n; ++i) {
      cin >> h[i + 1];
    }
    ++n;

    int s = 0;
    int b = 10000000 + 1;
    while (s + 1 < b) {
      int c = (s + b) / 2;
      if (sim(c, n)) b = c;
      else s = c;
    }
    static int cnt = 0;
    cout << "Case " << ++cnt << ": " << b << endl;
  }
  return 0;
}