貪心法――乘船問題
來源：程序員人生 發布時間：2015-03-11 08:39:49 閱讀次數：4515次
題目大致是：
有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);
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
