1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] arr数组-存储每位师傅每天能加工的零件数量,最多支持300个元素(适配n≤100的数据范围) int arr[300]; // [2] 降序排序的比较函数:用于将师傅的日产量从高到低排序,优先选择产量高的师傅以减少人数 bool cmp(int x,int y){ return x>y; } int main(){ // [3] m-需要加工的总零件数(m≤1e6);n-工厂的师傅总数(n≤100) int n,m; cin>>m>>n; // [4] 读取n位师傅的日产量,存入arr数组 for(int i=0;i<n;i++) cin>>arr[i]; // [5] 对师傅的日产量进行降序排序:贪心策略的核心,优先选择产量高的师傅,能最快满足总零件需求,从而减少需要的人数 sort(arr,arr+n,cmp); // [6] sum-累加已选师傅的日产量总和;sum1-统计已选的师傅人数;flag-标记是否能满足需求(1=能,0=不能) int sum=0; int sum1=0; int flag=0; // [7] 遍历降序后的师傅列表,依次选择产量最高的师傅,直到累计产量≥总需求 for(int i=0;i<n;i++){ sum+=arr[i]; // 累加当前师傅的日产量 sum1++; // 已选人数+1 if(sum>=m){ // 若累计产量≥总需求,说明已找到最少人数 flag=1; break; } } // [8] 根据flag判断输出:能满足需求则输出需要的人数,否则输出NO if(flag)cout<<sum1; else cout<<"NO"; return 0; }
- 1
信息
- ID
- 1033
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者