P76022 拿走过半 — 题解

专题： 排序与贪心
适用题目： 新生 OJ 本地题包中的 P76022，不要直接用于外站同名题。

解题思路

要让取走的硬币数过半且堆数最少，优先拿走硬币最多的堆。

复杂度

时间 $O(n\log n)$，额外空间 $O(n)$。

易错点

条件是严格大于一半，不是大于或等于。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int cmp_ll_asc(const void *p, const void *q) {
    long long a = *(const long long *)p, b = *(const long long *)q;
    return (a > b) - (a < b);
}
int cmp_ll_desc(const void *p, const void *q) {
    long long a = *(const long long *)p, b = *(const long long *)q;
    return (b > a) - (b < a);
}

int main(void) {
    int n;scanf("%d",&n);long long *a=malloc(n*sizeof(long long)),total=0;
    for(int i=0;i<n;i++){scanf("%lld",&a[i]);total+=a[i];}
    qsort(a,n,sizeof(long long),cmp_ll_desc);
    long long got=0;
    for(int i=0;i<n;i++){
        got+=a[i];if(got*2>total){printf("%d\n",i+1);break;}
    }
    free(a);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<ll> a(n);
    ll sum=0;
    for(auto&x:a){
        cin>>x;
        sum+=x;
    }
    sort(a.rbegin(),a.rend());
    ll take=0;
    for(int j=0;j<n;j++){
        take+=a[j];
        if(2*take>sum){
            cout<<j+1<<nl;
            break;
        }
    }
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。