TopCoder SRM 681 Div1 Easy: FleetFunding
解法
n=50, m=100000, k=1000000 なので O(nm log(k)) が間に合う。
2分探索 -> 貪欲はよく見る気がする。
コード
#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; } };