SRM548 Div1 Easy

250

二分探索する。

view plainprint?

1. bool ascending(vector<lli> H)  
2. {  
3.   for (int i = 1; i < H.size(); ++i) {  
4.     if (H[i - 1] < H[i]) continue;  
5.     return false;  
6.   }  
7.   return true;  
8. }  
9.   
10. bool solve(vector<lli> H, lli x)  
11. {  
12.   H[0] = max(1LL, H[0] - x);  
13.   for (int i = 1; i < H.size(); ++i) {  
14.     if (H[i - 1] < H[i]) {  
15.       H[i] = max(H[i - 1] + 1, H[i] - x);  
16.     } else {  
17.       H[i] = min(H[i - 1] + 1, H[i] + x);  
18.     }  
19.   }  
20.   
21.   return ascending(H);  
22. }  
23.   
24. class KingdomAndTrees {  
25. public:  
26.   int minLevel(vector <int> H_)  
27.   {  
28.     vector<lli> H;  
29.     for (int i = 0; i < H_.size(); ++i) {  
30.       H.push_back(H_[i]);  
31.     }  
32.   
33.     if (ascending(H)) return 0;  
34.   
35.     lli small = 0, large = 1000000000;  
36.     while (small + 1 < large) {  
37.       lli mid = (small + large) / 2LL;  
38.       if (solve(H, mid)) large = mid;  
39.       else small = mid;  
40.     }  
41.     return large;  
42.   }  
43. };  

bool ascending(vector<lli> H)
{
  for (int i = 1; i < H.size(); ++i) {
    if (H[i - 1] < H[i]) continue;
    return false;
  }
  return true;
}

bool solve(vector<lli> H, lli x)
{
  H[0] = max(1LL, H[0] - x);
  for (int i = 1; i < H.size(); ++i) {
    if (H[i - 1] < H[i]) {
      H[i] = max(H[i - 1] + 1, H[i] - x);
    } else {
      H[i] = min(H[i - 1] + 1, H[i] + x);
    }
  }

  return ascending(H);
}

class KingdomAndTrees {
public:
  int minLevel(vector <int> H_)
  {
    vector<lli> H;
    for (int i = 0; i < H_.size(); ++i) {
      H.push_back(H_[i]);
    }

    if (ascending(H)) return 0;

    lli small = 0, large = 1000000000;
    while (small + 1 < large) {
      lli mid = (small + large) / 2LL;
      if (solve(H, mid)) large = mid;
      else small = mid;
    }
    return large;
  }
};