APIO 2015 - Palembang Bridges

Time Complexity: $\mathcal{O}(N\log N)$

Since people only cross bridges when their two buildings are on opposite sides of the river, assume without loss of generality that all the people must cross a bridge.

$K=1$

If the bridge is at position $x$, then the total cost would be ${\sum }_{i=1}^N(|S_i-x|+|T_i-x|)$. Clearly, this value is minimized when $x$ is the median of all $S_i$ and $T_i$.

We can find the median simply by sorting all the numbers in the input.

$K=2$

Since each person crosses exactly one bridge, which one would person $i$ choose? The answer is that they'd choose the bridge that is closest to $\frac{S_i+T_i}{2}$.

This means that if we sort the people by $S_i+T_i$, then we can split them into a prefix where people choose bridge 1 and a suffix where people choose bridge 2. Notice how we can use our solution for $K=1$ to compute the answer for each bridge.

Now we can simply try out all the places to split the people into prefix and suffix. To maintain a sliding median, we can use two std::priority_queues. (For more details, see CSES Sliding Median)

1#include <bits/stdc++.h>
2#define FOR(i, x, y) for (int i = x; i < y; i++)
3typedef long long ll;
4using namespace std;
5 
6bool cmp(pair<int, int> a, pair<int, int> b) { return a.first + a.second < b.first + b.second; }
7
8priority_queue<int> lpq;
9priority_queue<int, vector<int>, greater<int>> rpq;
10ll lsum, rsum;