獨木舟上的旅行

時間限制：3000 ms ?|? 內(nèi)存限制：65535 KB 難度：2 ???? 描述

進行一次獨木舟的旅行活動，獨木舟可以在港口租到，并且之間沒有區(qū)別。一條獨木舟最多只能乘坐兩個人，且乘客的總重量不能超過獨木舟的最大承載量。我們要盡量減少這次活動中的花銷，所以要找出可以安置所有旅客的最少的獨木舟條數(shù)?，F(xiàn)在請寫一個程序，讀入獨木舟的最大承載量、旅客數(shù)目和每位旅客的重量。根據(jù)給出的規(guī)則，計算要安置所有旅客必須的最少的獨木舟條數(shù)，并輸出結(jié)果。

輸入

第一行輸入s,表示測試數(shù)據(jù)的組數(shù)；
每組數(shù)據(jù)的第一行包括兩個整數(shù)w，n，80<=w<=200,1<=n<=300，w為一條獨木舟的最大承載量,n為人數(shù)；
接下來的一組數(shù)據(jù)為每個人的重量（不能大于船的承載量）；

輸出

每組人數(shù)所需要的最少獨木舟的條數(shù)。

樣例輸入

3 85 6 5 84 85 80 84 83 90 3 90 45 60 100 5 50 50 90 40 60

樣例輸出

5 3 3

先把各個人的體重排序，然后計算最重的人和最輕的人能否同乘一條舟，如果不能，則最重的人就要單獨乘坐一條舟，再求最輕的和第二重的人的和，依次比較。

AC代碼如下：

#include<stdio.h> int main() {int n,w,m,i,a[300],t;scanf("%d",&n);while(n--){scanf("%d%d",&w,&m);int k=0,j=0;for(i=0;i<m;i++)scanf("%d",&a[i]);for(i=0;i<m;i++)for(j=i+1;j<m;j++)if(a[i]>a[j]){t=a[i];a[i]=a[j];a[j]=t;} /*對體重排序*/for(i=0,j=m-1;i<=j;){if(a[i]+a[j]<=w){i++;j--;k++;} /*如果可以，讓他們兩個同乘一條，再比較第二輕和第二重的人，以此類推*/else if(i==j)k++; /*就剩一個人的時候，他自己單獨一條*/else {j--;k++;} /*重的人自己單獨一條舟*/ }printf("%d\n",k);}return 0; }

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的NYOJ 71 独木舟上的旅行 贪心算法 之 乘船问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。