TopCoder SRM 681 Div1 Easy: FleetFunding

解法

n=50, m=100000, k=1000000 なので O(nm log(k)) が間に合う。

2分探索 -> 貪欲はよく見る気がする。

類題: D: 壊れた電車 - CODE FESTIVAL 2015 予選A | AtCoder

コード

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
#include <map>

using namespace std;

class FleetFunding {
 public:
  bool ok(const vector<int> &k, const vector<int> &a, const vector<int> &b,
          int mid, int m, const vector<pair<int, int>> &b_sort) {
    int n = b_sort.size();
    vector<int> l(k);
    for (int i = 1; i <= m; ++i) {
      int rest = mid;
      for (int j = 0; j < n; ++j) {
        int I = b_sort[j].second;
        if (b[I] < i || a[I] > i) continue;
        if (rest > l[I]) {
          rest -= l[I];
          l[I] = 0;
        } else {
          l[I] -= rest;
          rest = 0;
          break;
        }
      }
      if (rest > 0) return false;
    }
    return true;
  }

  int maxShips(int m, vector<int> k, vector<int> a, vector<int> b) {
    int n = k.size();
    vector<pair<int, int>> b_sort(n);
    for (int i = 0; i < n; ++i) {
      b_sort[i] = {b[i], i};
    }
    sort(b_sort.begin(), b_sort.end());

    int high = 100000000;
    int low = 0;
    while (high > low + 1) {
      const int mid = (high + low) / 2;
      if (ok(k, a, b, mid, m, b_sort))
        low = mid;
      else
        high = mid;
    }
    return low;
  }
};