SRM 329 Div1 Medium LogCutter

問題

長さLの丸太がある。この丸太はK箇所で切断でき、位置はであたえられる。この丸太を最大C箇所で切断できるとした時に、もっとも長い丸太を最小化せよ。返す値は最小化した値と最初に切断する位置とせよ。最初の切断位置が複数取れる場合は最も小さい値を返せ。

やりかた

最小値にかんする二分探索＋貪欲。
まずはカットできる位置を列挙してソートして持っておく。その上で最小化した長さに関して二分探索を行う。二分探索で探査する値を決めて、カットできる位置が大きい方から貪欲に、なるべく断片が長くなるようにカットして、カット回数が上限を超えるか調べる。後ろ側から調べるのは、こうすることで、最も手前側のカット地点が小さくなるから。
なお、もしもカットする回数を余るようなら、最も手前の位置で余分にカットを入れる。

以下ソース。

vector<ll> p;

class LogCutter {
public:
  string i2s(ll a){
    stringstream ss;
    ss << a;
    string ret;
    ss >> ret; 
    return ret;
  }
  ll check(ll w, int c){
    ll cnt = 0, pos = p.back(), first = p.back();
    for(int i = (int)p.size() - 1; i >= 1; i--){
      if(p[i] - p[i - 1] > w) return LLINF;
      if(pos - p[i - 1] > w){
	pos = p[i];
	first = min(first, pos);
	cnt++;
      }
      if(cnt > c) return LLINF;
    }

    if(c - cnt > 0) return p[1];//カットする回数が余ったら一番手前にカットを入れる
    return first;
  }
  string bestCut(int L, int A, int K, int C){
    p.clear();
    p.push_back(0);
    p.push_back(L);
    for(ll i = 1; i <= K; i++) p.push_back((ll)(i * A) % (L - 1) + 1);
    sort(ALL(p));

    ll ub = LLINF, lb = 0, firstcut = LLINF;
    while(ub - lb > 1){
      ll mid = (ub + lb) / 2LL;
      firstcut = check(mid, C);
      if(firstcut == LLINF) lb = mid;
      else ub = mid;
    }
    return i2s(ub) + " " + i2s(check(ub, C));
  }
};