P76023 十二个月的增长 — 题解

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

解题思路

把每个月的增长量降序排列，优先使用贡献最大的月份，累计到达到 k。

复杂度

排序 12 个数，时间 $O(12\log 12)$。

易错点

k=0 时无需任何月份；全年总和不足应输出 -1。

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 k;scanf("%d",&k);long long a[12];
    for(int i=0;i<12;i++)scanf("%lld",&a[i]);
    qsort(a,12,sizeof(long long),cmp_ll_desc);
    if(k==0){puts("0");return 0;}
    long long sum=0;int ans=-1;
    for(int i=0;i<12;i++){
        sum+=a[i];if(sum>=k){ans=i+1;break;}
    }
    printf("%d\n",ans);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 k;
    cin>>k;
    vector<int>a(12);
    for(auto&x:a)cin>>x;
    sort(a.rbegin(),a.rend());
    if(k==0){
        cout<<0<<nl;
        return 0;
    }
    int sum=0,ans=-1;
    for(int j=0;j<12;j++){
        sum+=a[j];
        if(sum>=k){
            ans=j+1;
            break;
        }
    }
    cout<<ans<<nl;
    return 0;
}

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