1 条题解
-
0
#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
- 上传者