题解：P8134 [ICPC 2020 WF] Opportunity Cost

· · 题解

题意

题目清晰，不再赘述。

做法

设 P_{i,k} 表示第 i 部手机第 k 维属性，即 1 表示 x，以此类推。

考虑将题目直接形式化，即求这个：

\min_{j=1}^n \max_{i=1}^n \sum_{k=1}^3 \max(P_{i,k}-P_{j,k},0)

考虑这样一个东西：

\sum_{k=1}^3 \max(a_{i,k},0)

可以将这个视作对于每个 a_{i,k} 选或不选，这个可以显然的考虑到子集枚举的形式，于是上式可以转化成：

\min_{j=1}^n \max_{i=1}^n \max_{S \subset{1,2,3}}\sum_{k \in S}P_{i,k}-P_{j,k} \min_{j=1}^n \max_{S \subset{1,2,3}}\sum_{k \in S}(\max_{i=1}^n P_{i,k})-P_{j,k}

这样就把对于 i 的枚举可以拉出来先预处理，然后循环枚举 j 去做即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define DF(i,a,b) for(int i=(a);i>=(b);i--)
const int N=2e5+10;
int n,A[8],B[8][N],tmp[N],ans=1e18,id;
struct node{int x,y,z;}a[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    F(i,1,n){
        int x,y,z;cin>>x>>y>>z;
        a[i]={x,y,z};
    }
    F(msk,0,7){
        F(i,1,n)tmp[i]=0;
        if(msk&1)F(i,1,n)tmp[i]+=a[i].x;
        if(msk&2)F(i,1,n)tmp[i]+=a[i].y;
        if(msk&4)F(i,1,n)tmp[i]+=a[i].z;
        F(i,1,n)A[msk]=max(A[msk],tmp[i]),B[msk][i]=tmp[i];
    }
    F(j,1,n){
        int res=0;
        F(msk,0,7)res=max(res,A[msk]-B[msk][j]);
        if(res<ans)ans=res,id=j;
    }
    cout<<ans<<" "<<id<<"\n";
    return 0;
}