DDCC2017 予選C: C - 収納

問題

C - 収納

解説

本の棒をすべて収納する必要がある。大きい棒を基準に小さい棒を埋め合わせるようにした方が良い。 本入れられる場合、最も大きい棒と最も小さい棒のペアから、大きい棒を入れることを優先として収納していくのが最適。小さい棒が入らなかったら、次に大きい棒とのペアを試していく。

ABC[ARC]基準で200点という印象。

int main() {
  int N, C; cin >> N >> C;
  vector<int> L(N); cin >> L;
  sort(all(L));
  int left = 0;
  int ans = 0;
  for (int right = N - 1; right >= left; right--) {
    if (L[right] + L[left] + 1 <= C) {
      left++;
    }
    ans++;
  }
  cout << ans << endl;
}