自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 22:36:17，当前版本为作者最后更新于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;
}