高质量题解|最优装载问题

题目大意

在载重量 $C$ 之内求得最多能获取的古董数量

考纲知识点

输入输出、分支结构、循环结构、一维数组、算术运算符、$sort$ 排序、自定义函数、贪心算法、基础数据类型、变量的定义以及使用

解题思路

要想获取更多的古董，就需要保持古董的重量不超过载重量 $C$ ，所以古董的重量越小越好
用 $sort$ 排序从小到大升序排序，排序后就是古董重量小的排在前面
定义一个 $cnt$ 变量记录目前可以装的古董数量，$sum$ 记录当前的重量
如果古董目前的重量和要加的古董重量超出了海盗船的载重量 $C$ ，就结束循环
没有超过载重量 $C$ 就让 $sum$ 加上这个古董的重量，$cnt$ 自增

参考程序

#include <bits/stdc++.h>
using namespace std;
int a[1010];
int main(){
    int c,n;
    cin >> c >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    sort(a + 1,a + n + 1);
    int cnt = 0,sum = 0;
    for(int i = 1;i <= n;i++){
        if((a[i] + sum) > c){
            break;
        }else{
            sum += a[i];
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

时间复杂度

$O(n$ log $n)$(线性对数时间复杂度)

空间复杂度

$O(n)$(线性空间复杂度)