有 n 个人, 第 i 个人的重量为 w[i], 每艘船的最大载重量均为 c, 且最多只能乘两个人. 用最少的船装载所有人.
思路: 从最轻的开始考虑, 让最轻的和最重的一条船, 若超出重量则可判定最重的只能一人一条船
代码:
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int n,m;
- int a[100];
- int main()
- {
- cin>>n>>m;//n 为人数, m 为一条船的最大承重
- for(int i=1;i<=n;i++) cin>>a[i];
- sort(a+1,a+n+1);
- int i=1,j=n;
- int ans=0;
- while(i<j)
- {
- if(a[i]+a[j]>m) j--;
- else
- {
- i++;
- j--;
- ans++;
- }
- }
- cout<<ans+n-2*ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2589858.html