MOVE12 - VOI 2012 Điều động

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int N = 10000;
int c[N], t[N], n;

bool ok(int timeLimit) {
	vector<pair<int, int> > limit (n);
	for(int i = 0; i < n; ++i)
		limit[i] = make_pair(max(0, c[i] - timeLimit / t[i]), min(n - 1, c[i] + timeLimit / t[i]));
	sort(limit.begin(), limit.end());
	priority_queue<int> q;
	for(int pos = 0, x = 0; pos < n; ++pos) {
		while(x < n && limit[x].first <= pos)
			q.push(-limit[x++].second);
		if(q.empty() || pos > -q.top()) return false;
		q.pop();
	}
	return true;
}

void enter() {
	cin >> n;
	for(int i = 0; i < n; ++i)
		cin >> c[i] >> t[i], --c[i];
}

void solve() {
	int low = 0, high = 1e9;
	while(low < high) {
		int mid = (low + high) >> 1;
		if(ok(mid)) high = mid;
		else low = mid + 1;
	}
	cout << low << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	enter();
	solve();
	return 0;
}

Download