|
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <stack> using namespace std; int main(){ int l = 0,n = 0,m = 0; vector<int> rock; while (cin >> l >> n >> m) { for (int i = 1; i <= n; i++) { int tmp; scanf(" %d",&tmp); rock.push_back(tmp); } rock.push_back(l); rock.push_back(0); sort(rock.begin(), rock.end()); int high = l,low = 0,mid = l/2; int ans = 0; while (high >= low) { mid = (high+low)/2; int cnt = 0,prev = 0; for (int i = 1; i < rock.size(); i++) { if (rock[i] - rock[prev] < mid) { cnt++; }else { prev = i; } } if (cnt > m) { high = mid-1; }else{ ans = mid; low = mid+1; } } cout << ans << endl; } return 0; } |
二分不会啊。。。
