题解：P11383 [POI 2024/2025 R1] Sprawiedliwy podział

Co_Ce · 2025-01-24 21:03:19 · 题解

注：本题解只抛砖引玉，代码只能得 40 pts。

link

首先，将物品按 a_i+b_i 排序。
接下来，如果 Bajtyna 的所得价值大于 Bitek 的所的价值，就把第 i 个物品分给 Bitek，否则分给 Bajtyna。并用 ans_i 标记。

std：

#include<bits/stdc++.h>
#define maxn 500010

using namespace std;

int n;//物品的数量

long long suma=0,sumb=0;

bool ans[maxn];//0 Bajtyna

struct item{
    int a,b;//a表示每件物品对 Bajtyna 的价值 b表示每件物品对 Bitek 的价值
    int num;//序号 
}items[maxn];

bool cmp(const item &x,const item &y){
    return (x.a+x.b)>(y.a+y.b);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>items[i].a;
        items[i].num=i;
    }
    for(int i=1;i<=n;i++){
        cin>>items[i].b;
    }
    sort(items+1,items+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(suma+items[i].a<=sumb+items[i].b){
            suma+=items[i].a;
            ans[items[i].num]=1;
        }
        else{
            sumb+=items[i].b;
            ans[items[i].num]=0;
        }
    }
    for(int i=1;i<=n;i++){
        if(ans[i]){
            cout<<1<<" ";
            continue;
        }
        cout<<0<<" ";
    }
    return 0;
}