贪心法――乘船问题
来源：程序员人生 发布时间：2015-03-11 08:39:49 阅读次数：4336次
题目大致是：
有n个人，第i个人的重量为w[i]，每艘船的最大载重量均为c，且最多只能乘两个人。用最少的船装载所有人。
解：
首先从最轻的人开始斟酌，那末他应当和最重的人去坐，如果每一个人都不能和它坐船，那末唯1的方法就是每一个人做1艘船。
否则，他应当选择能够和他1起坐船的人中最重的那个，这模样才不会浪费。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct node{
int w;
}a[1001];
bool cmp(node a,node b){
return a.w<b.w;
}
int main(){
int i,j,n,c;
int book[1001]={0};
scanf("%d%d",&n,&c);
for(i=1;i<=n;i++)
scanf("%d",&a[i].w);
sort(a+1,a+1+n,cmp);
int num=0;
for(i=1;i<=n;i++){
//book[i]=1;
for(j=n;j>=1;j--){
//one:如果它们两个的重量和小于等于c的话，并且j这个人没有被其他人给拉去，那末这是1种；
if(a[i].w+a[j].w<=c && book[j]==0){
num++; book[i]=1; book[j]=1; break;
}
//two:如果它们两个的重量和大于c的话且j这个人没有被拉去，那末j那个人只能自己和自己1个人坐1条船了；
else if(a[i].w+a[j].w>c && book[j]==0){
num++; book[j]=1;
}
}
//如果上面的都循环完了，但是i还是没有满足的条件，那末说明它也只能自己坐1条船了；
if(!book[i]) {num++; book[i]=1;}
}
printf("%d
",num);
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
