合肥市第33屆信息學競賽（2016年）
題目描述 Description
卡卡西和小朋友們要乘船過河了，港口有很多條船可以租到，并且之間沒有區別，每條船的出租費用也是一樣的。但是一條船最多只能乘坐兩個人，且乘客的總重量不能超過船的最大承載量。我們要找出可以安置所有小朋友的最小船數以降低總的租船費用，卡卡西很快的寫出了一個程序，讀入船的最大承載量、旅客數目和每位旅客的重量，計算出要安置所有同學必須的最少的船的數目。
輸入描述 Input Description
輸入數據有兩行。第一行兩個整數w和n，用空格分隔，分別表示一條船的最大承載量和人數；第二行中每個數據是每個人的重量，也是整數，數據間用空格分隔。
輸出描述 Output Description
最小船數。
樣例輸入 Sample Input
【輸入樣例一】 85 6 5 84 85 80 84 83 【輸入樣例二】 100 5 50 50 90 40 60
樣例輸出 Sample Output
【輸出樣例一】 5 【輸出樣例 二】 3
數據范圍及提示 Data Size & Hint
3≤w≤200，3≤n≤300 每位乘客的重量都不大于船的承載量。
#include<bits/stdc++.h>
using namespace std;
int a[310],s=0,w,n;
int main(){cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);for(int i=1,j=n;i<=j;){if(a[i]+a[j]<=w){i++,j--;}else{j--;}s++;}cout<<s;return 0;
}
)
