贪心法――乘船问题
发布时间：2020-12-13 20:15:30 所属栏目：PHP教程 来源：网络整理
导读：题目大致是： 有n个人，第i个人的重量为w[i]，每艘船的最大载重量均为c，且最多只能乘两个人。用最少的船装载所有人。 解： 首先从最轻的人开始斟酌，那末他应当和最重的人去坐，如果每一个人都不能和它坐船，那末唯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);
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |