[AGC040D] Balance Beam
颇有难度的一道题。
首先思考我们的手上有什么武器可以使用。发现如果石板的排列确定下来，那么合法的 B 一定是形如 \([0, x)\) 的一段区间。我们只需令 \(x\) 最大即可。同时，显然可以认为终点一定在整点上。题目中很为难我们的一点是位置并不是离散的，所以自然想到图像。但是我没想到图像，所以只好先假装位置是离散的看一下有什么做法。
考虑寻找充要条件，假设 B 从 \(x\) 点，在 \(y\) 点被逮住，那么充要条件是：
\[\sum_{i \le y} A_i \le \sum_{x < i \le y} B_i
\]
考虑分离 \(x, y\) 这两个变量。变为 \(\sum_{i \le x} A_i + \sum_{x < i \le y} (A_i - B_i) \le 0\)
好了，现在把排列丢掉，问题转化为划分两个不交的集合 \(S, T\) 使得
\[s = \sum_{i \in S} A_i + \sum_{i \in T} (A_i - B_i) \le 0
\]
最大化 \(|S|\)。
这样就有一个简单的贪心做法了：注意到 \(A_i\) 一定是正的，而 \(A_i - B_i\) 可能是负的，所以初始把所有会使 \(s\) 减小的 \(i\) 划分入 \(T\)，然后贪心选代价最小的加入 \(S\)，直到不能选为止。
现在回到原问题，自然想到枚举分界点然后转化成上面的问题。怎么做呢？注意到由于终点一定是整点，所以分界点这一段必然要么处于 B 左侧，要么在 B 和终点中间。去掉这一段，我们希望选择尽可能多的整点，所以初始时先令 \(s\) 尽可能的小，然后在通过二分优化贪心地过程，最后单独算这个散段的最值就行了。什么叫令 \(s\) 尽可能的小呢？就是不管怎样都先加上一个当前段的 \(A_i - B_i\)，由于 \(i\) 要么出现在 \(S\) 中要么出现在 \(T\) 中，所以这个做法是正确的。
const int N = 1e5 + 10;
struct Frac {
LL x, y;
void check() {
LL d = __gcd(x, y);
x /= d, y /= d;
}
bool operator < (const Frac &rhs) const {
return (__int128)x * rhs.y < (__int128)rhs.x * y;
}
};
int n;
LL a[N], b[N];
struct item {
int id;
LL c;
}c[N];
int p[N];
LL pre[N];
int main() {
read(n);
for(int i = 1; i <= n; ++i)
read(a[i], b[i]);
LL sum = 0;
for(int i = 1; i <= n; ++i) {
c[i].id = i;
if(b[i] >= a[i]) {
sum += b[i] - a[i];
c[i].c = -b[i];
} else {
c[i].c = -a[i];
}
}
sort(c + 1, c + n + 1, [](item x, item y) {
return x.c > y.c;
});
for(int i = 1; i <= n; ++i)
p[c[i].id] = i, pre[i] = pre[i - 1] + c[i].c;
Frac ans = {0, 1};
for(int i = 1; i <= n; ++i) {
LL s = sum;
if(b[i] < a[i]) s += b[i] - a[i];
int pos = 0;
for(int l = 1, r = n; l <= r; ) {
int mid = (l + r) / 2;
LL sum = pre[mid] - (mid >= p[i]) * c[p[i]].c;
if(s + sum >= 0) pos = mid, l = mid + 1;
else r = mid - 1;
}
LL sum = s + (pre[pos] - (pos >= p[i]) * c[p[i]].c);
Frac res;
res = (Frac){(pos - (pos >= p[i])) * b[i] + min(sum, b[i]), b[i]};
if(res.x < 0) continue;
res.check();
if(ans < res) ans = res;
}
ans.y *= n;
ans.check();
printf("%lld %lld\n",ans.x,ans.y);
}