题解：P8134 [ICPC 2020 WF] Opportunity Cost

思路

先考虑暴力思路，枚举每个手机 \(i\)，然后找一个手机 \(j\)，满足 \(\max \left(x_{j}-x_{i}, 0\right)+\max \left(y_{j}-y_{i}, 0\right)+\max \left(z_{j}-z_{i}, 0\right)\) 最大。于是就有了暴力枚举手机 \(j\) 的 \(O(n^2)\) 做法，喜提罚时。

接下来考虑优化。不难发现，题目实际上是在求：

\[\min_{1\le i\le n}\{\max _{1 \leq j \leq n}\{\max \left(x_{j}-x_{i}, 0\right)+\max \left(y_{j}-y_{i}, 0\right)+\max \left(z_{j}-z_{i}, 0\right)\}\} \]

而目前的瓶颈在于：

\[\max _{1 \leq j \leq n}\{\max \left(x_{j}-x_{i}, 0\right)+\max \left(y_{j}-y_{i}, 0\right)+\max \left(z_{j}-z_{i}, 0\right)\} \]

我们希望加速找到使得答案最大的 \(j\) 的过程，但仔细想想，发现是不太可能且比较复杂的。于是我们考虑优化这个式子。

显然，对于式子中的每个 \(\max\)，其返回值要么为 \(0\)，要么大于 \(0\)，那么式子中的三个 \(\max\) 就有 \(2^3=8\) 种情况，可以做分类讨论。

首先，对于这 \(8\) 种情况，我们可以用二进制来表示，其数值范围在 \(0\) 到 \(7\)。若第 \(i\) 位（从 \(0\) 开始）为 \(1\)，则代表式子中第 \(i+1\) 个 \(\max\) 返回值大于 \(0\)，反之等于 \(0\)。为了方便讲述，下面我将用 \(u_i\) 表示第 \(i+1\) 位是否为 \(1\)。

然后，对于每种情况，我们需要找到：

\[\max _{1 \leq i \leq n}\{u_{1}\times x_{i}+u_{2}\times y_{i}+u_{3}\times z_{i}\} \]

这样就可以在 \(O(n)\) 的时间内预处理这 \(8\) 种情况，我们用 \(b_j\) 来表示。

最后，枚举每一个手机，代入每种情况，求出每种情况中可以得到的最大贡献，然后更新答案即可。具体来说，就是在找：

\[\min_{1\leq i\le n}\{\max _{0 \leq j \leq 7}\{b_j-\left(u_{1}\times x_{i}+u_{2}\times y_{i}+u_{3}\times z_{i} \right)\}\} \]

可能给一些人带来的疑惑在于，对于一种情况 \(b_j\)，假设使其最大的是手机 \(k\)，而当前枚举的手机 \(i\) 又满足 \(x_k-x_i<0\) 或 \(y_k-y_i<0,z_k-z_i<0\)，这是否会影响正确性？其实是不会的。对于 \(x_k-x_i<0\) 的情况，已经涵盖在 \(u_1=0\) 的情况之中了，而当前情况又算了负数的贡献，自然是不优的，所以不影响答案的正确性。

这样我们就可以在 \(O(n)\) 的时间内求出答案。

代码

#include<bits/stdc++.h>
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define fi first
#define se second
#define in(a) a = read_int()
using namespace std;
typedef long long ll;
const int Size = 1 << 14;
const int N = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f; 
inline int read_int() {int x = 0;char ch = getchar();bool f = 0;while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();return f ? -x : x;
}
ll a[N][3] , b[8];
signed main() {//cin_fast;int n;in(n);for(int i = 1 ; i <= n ; i ++) {in(a[i][0]) , in(a[i][1]) , in(a[i][2]);}for(int i = 1 ; i <= n ; i ++) {for(int j = 0 ; j <= 7 ; j ++) {ll h = 0;for(int k = 0 ; k <= 2 ; k ++) {if((1 << k) & j) h += a[i][k];}b[j] = max(b[j] , h);}}ll ans = INF , id;for(int i = 1 ; i <= n ; i ++) {ll now = 0;for(int j = 0 ; j <= 7 ; j ++) {ll h = 0;for(int k = 0 ; k <= 2 ; k ++) {if((1 << k) & j) h += a[i][k];}now = max(now , b[j] - h);}if(ans > now) {ans = now;id = i;}}cout << ans << ' ' << id;return 0;
}