1 条题解

  • 0
    @ 2026-1-28 12:47:44
    #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
    上传者