题解：P13753 【MX-X17-T2】The median of sum

问题分析

本题要求将数组元素不重不漏地划分为任意数量的组，使得所有组和的中位数（第

\lfloor\frac{k+1}{2}\rfloor

小的数）最小。通过分析可知，中位数的位置与分组数量

k

相关，我们需要找到最优的分组策略来最小化这个中位数。

思路

关键观察：
- 当所有元素均为非负数时，最优策略是将最小元素单独分为一组，其余元素分成另一组。此时排序后第 $\lfloor\frac{n+1}{2}\rfloor$ 小的元素就是数组的最小元素。
- 当存在负数时，最优策略是将所有负数合并为一组，正数单独成组。此时负数组的和会成为中位数（或更靠前的位置），且这是能得到的最小可能值。
算法步骤：
- 对数组进行排序，便于快速获取最小元素和区分正负。
- 若数组最小元素为非负数，直接输出该最小元素。
- 若存在负数，计算所有负数的和并输出。

AC代码

CPP

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        sort(a+1,a+n+1);  // 排序数组，便于处理
        if(a[1]>=0){  // 所有元素非负的情况
            cout<<a[1]<<"\n";
        }
        else{  // 存在负数的情况
            long long ans=0;
            for(int i=1;i<=n;i++){
                if(a[i]<=-1){  // 累加所有负数
                    ans+=a[i];
                }
            }
            cout<<ans<<"\n";
        }
    }
    return 0;\\完美结束
}

题解：P13753 【MX-X17-T2】The median of sum

文章操作

问题分析

思路

AC代码

相关推荐

评论

题解：P13753 【MX-X17-T2】The median of sum