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

· · 题解

问题分析

本题要求将数组元素不重不漏地划分为任意数量的组，使得所有组和的中位数（第\lfloor\frac{k+1}{2}\rfloor小的数）最小。通过分析可知，中位数的位置与分组数量k相关，我们需要找到最优的分组策略来最小化这个中位数。

思路

  1. 关键观察：

    • 当所有元素均为非负数时，最优策略是将最小元素单独分为一组，其余元素分成另一组。此时排序后第\lfloor\frac{n+1}{2}\rfloor小的元素就是数组的最小元素。
    • 当存在负数时，最优策略是将所有负数合并为一组，正数单独成组。此时负数组的和会成为中位数（或更靠前的位置），且这是能得到的最小可能值。

  2. 算法步骤：

    • 对数组进行排序，便于快速获取最小元素和区分正负。
    • 若数组最小元素为非负数，直接输出该最小元素。
    • 若存在负数，计算所有负数的和并输出。

AC代码

#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;\\完美结束
}