P76021 清仓收益 — 题解

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

解题思路

只有负价格才能带来收益，因此排序后从最负的数起最多取 m 个。

复杂度

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

易错点

没有负价格时答案是 0，不必凑够 m 件。

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,m;scanf("%d%d",&n,&m);long long *a=malloc(n*sizeof(long long));
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    qsort(a,n,sizeof(long long),cmp_ll_asc);
    long long ans=0;
    for(int i=0;i<m && a[i]<0;i++)ans-=a[i];
    printf("%lld\n",ans);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,m;
    cin>>n>>m;
    vector<ll> a(n);
    for(auto&x:a)cin>>x;
    sort(a.begin(),a.end());
    ll ans=0;
    for(int i=0;i<m&&a[i]<0;i++)ans-=a[i];
    cout<<ans<<nl;
    return 0;
}

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