1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| #include <vector> #include <algorithm> using namespace std; int SIZE;
inline bool is_possible(vector<int>& rocks, int &stnd, int &n, int &dis){ register int removed = 0, prev = 0, i; for(i=0;i<SIZE;i++) rocks[i]-prev<stnd ? ++removed : prev = rocks[i]; return dis-rocks[i-1]<stnd ? ++removed<=n : removed<=n; } int solution(int distance, vector<int> rocks, int n) { sort(rocks.begin(),rocks.end()); SIZE = rocks.size(); register int lo = 1, hi = distance, mid; while(lo+1<hi){ mid = (lo+hi)>>1; is_possible(rocks,mid,n,distance) ? lo = mid : hi = mid ; } return is_possible(rocks,lo,n,distance) ? lo : hi; }
|