题解：P8134 [ICPC 2020 WF] Opportunity Cost

fish_love_cat · 2025-07-20 00:52:02 · 题解

KDL：做不做 Ad-hoc？

于是有了这篇题解。

观察题面这个式子，注意到三个取最大之间是用加号连接的，这启示我们拆式子进行分讨。

我们对于每一个取最大的运算取到的值进行分讨，总共三个，组合一下共有 8 种情况。

然后我们知道原式的值就是八个互不影响的情况的最大值。于是分别对于每一种情况进行考虑。

观察现在这个式子的形式，注意到每次被减数一定是其他手机某些参数的和，而每个情况这个和的最大值是固定的。

由于只看最大值，所以最后的值只与最大的被减数挂钩。

这启示我们对每个情况预处理最大的被减数即可，然后扫一遍所有手机求答案。

做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200005][3];
int b[200005][9];
int mx[9];
int ans=1e18,flc;
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
        for(int j=1;j<=8;j++){
            for(int k=0;k<=2;k++)
                b[i][j]+=((j>>k)&1)*a[i][k];
            mx[j]=max(mx[j],b[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        int qwq=0;
        for(int j=1;j<=8;j++)
            qwq=max(qwq,mx[j]-b[i][j]);
        if(ans>qwq)ans=qwq,flc=i;
    }cout<<ans<<' '<<flc;
}