1 条题解

  • 0
    @ 2026-1-28 12:35:18
    #include <bits/stdc++.h>
    using namespace std;
    
    // [1] arr数组-存储每个乘客的重量,最多支持11000个元素(适配n≤1000的数据范围)
    int arr[11000];
    
    int main(){
        // [2] n-乘客的总人数
    	int n;
    	cin>>n;
        // [3] 读取n个乘客的重量,存入arr数组
    	for(int i=0;i<n;i++){
    		cin>>arr[i];
    	}
        // [4] c-独木舟的最大承载量(每条船最多坐2人,且总重量≤c)
    	int c;
    	cin>>c;
    	
        // [5] 对乘客重量进行升序排序:贪心策略的基础,通过排序让最轻和最重的乘客优先匹配,最大化船的利用率
    	sort(arr,arr+n);
    	
        // [6] l-左指针(指向当前最轻的乘客,初始为0);r-右指针(指向当前最重的乘客,初始为n-1);sum-统计最少需要的独木舟数量,初始为0
    	int l=0,r=n-1,sum=0;
        // [7] 双指针循环:从两端向中间遍历,处理所有乘客
    	while(l<=r){
            // [8] 贪心匹配:尝试让当前最轻和最重的乘客同乘一条船
            // 若两人总重量≤船的承载量,说明可以同乘,同时移动左右指针
    		if(arr[l]+arr[r]<=c){
    			l++,r--;
            // [9] 若两人总重量超过承载量,说明最重的乘客只能单独乘一条船,仅移动右指针
    		}else{
    			r--;
    		}
            // [10] 无论是否同乘,每处理一次就增加一条船的计数
    		sum++;
    	}
        // [11] 输出最少需要的独木舟数量
    	cout<<sum;	
    }
    
    • 1

    信息

    ID
    1027
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    2
    已通过
    2
    上传者