Skip to Content
CTRL K

Palembang Bridges

Explicación

Como las personas solo cruzan puentes cuando sus dos edificios están en lados opuestos del río, asumimos sin pérdida de generalidad que todas las personas deben cruzar un puente.

K=1K = 1

Si el puente está en la posición xx, entonces el costo total sería ∑i=1N(∣Si−x∣+∣Ti−x∣)\sum_{i = 1}^N (|S_i - x| + |T_i - x|). Claramente, este valor se minimiza cuando xx es la mediana de todos los SiS_i y TiT_i.

Podemos hallar la mediana simplemente ordenando todos los números de la entrada.

K=2K = 2

Como cada persona cruza exactamente un puente, ¿cuál elegiría la persona ii? La respuesta es que elegiría el puente más cercano a Si+Ti2\frac{S_i + T_i}{2}.

Esto significa que si ordenamos a las personas por Si+TiS_i + T_i, entonces podemos partirlas en un prefijo donde las personas eligen el puente 1 y un sufijo donde eligen el puente 2. Notamos que podemos usar nuestra solución para K=1K = 1 para calcular la respuesta de cada puente.

Ahora podemos simplemente probar todos los lugares para partir a las personas en prefijo y sufijo. Para mantener una mediana deslizante, podemos usar dos std::priority_queue. (Para más detalles, ver CSES Sliding Median )

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal O(N \log N)

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
 
bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.first + a.second < b.first + b.second;
}
 
priority_queue<int> lpq;
priority_queue<int, vector<int>, greater<int>> rpq;
ll lsum, rsum;
 
void insert(int x) {
	int median = (lpq.size() ? lpq.top() : 1000000001);
	if (x <= median) {
		lpq.push(x);
		lsum += x;
	} else {
		rpq.push(x);
		rsum += x;
	}
 
	if (rpq.size() + 1 < lpq.size()) {
		int nxt = lpq.top();
		lpq.pop();
		rpq.push(nxt);
		lsum -= nxt;
		rsum += nxt;
	} else if (lpq.size() < rpq.size()) {
		int nxt = rpq.top();
		rpq.pop();
		lpq.push(nxt);
		rsum -= nxt;
		lsum += nxt;
	}
}
 
ll pref[100001];
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int k, n;
	ll same_side = 0;
	vector<pair<int, int>> v = {{0, 0}};
	cin >> k >> n;
	FOR(i, 0, n) {
		char a, b;
		int x, y;
		cin >> a >> x >> b >> y;
		if (a == b) same_side += abs(x - y);
		else v.push_back({x, y});
	}
	sort(v.begin(), v.end(), cmp);
	n = v.size() - 1;
	same_side += n;
 
	lsum = rsum = 0;
	FOR(i, 1, n + 1) {
		insert(v[i].first);
		insert(v[i].second);
		pref[i] = rsum - lsum;
	}
 
	ll ans = pref[n];
 
	if (k == 2) {
		while (lpq.size()) lpq.pop();
		while (rpq.size()) rpq.pop();
		lsum = rsum = 0;
 
		for (int i = n; i; i--) {
			insert(v[i].first);
			insert(v[i].second);
			ans = min(ans, rsum - lsum + pref[i - 1]);
		}
	}
	cout << same_side + ans;
	return 0;
}
Fundamentos