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

weifengzhaomi · 2025-08-17 18:24:52 · 题解

思路

容易发现，中位数一定是所有负数之和或最小的整数。

怎么证明呢。

我们贪心的去想，如果有负数，那肯定是负数更优。

否则，肯定是最小的整数比其他整数更优。

代码

#include<bits/stdc++.h>
using namespace std;
int t,n,a[1000010],x[1000010],y[1000010],top,tot;
long long ans;
int main(){
    cin >> t;
    while (t--){
        scanf("%d",&n),top = tot = ans = 0;
        for (int i = 1;i <= n;i++) scanf("%d",&a[i]);
        for (int i = 1;i <= n;i++) if (a[i] >= 0) x[++top] = a[i]; else y[++tot] = a[i],ans += 1LL * a[i];
        if (tot) printf("%lld\n",ans);
        else sort(x + 1,x + top + 1),printf("%d\n",x[1]);
    }
}