基準時間限制:1 秒 空間限制:131072 KB 分值: 10 難度:2級算法題
收藏
關注n個人,已知每個人體重。獨木舟承重固定,每只獨木舟最多坐兩個人,可以坐一個人或者兩個人。顯然要求總重量不超過獨木舟承重,假設每個人體重也不超過獨木舟承重,問最少需要幾只獨木舟?Input第一行包含兩個正整數n (0<n<=10000)和m (0<m<=2000000000),表示人數和獨木舟的承重。接下來n行,每行一個正整數,表示每個人的體重。體重不超過1000000000,并且每個人的體重不超過m。Output一行一個整數表示最少需要的獨木舟數。Input示例3 6123Output示例2
//最重的和最輕的坐一只船 如果超重就先讓重的過去,否則就過去兩個人
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long LL;const int maxn = 10000 + 5;LL weight[maxn];int main(){ LL n,m; cin>>n>>m; for(int i=0;i<n;i++) { cin>>weight[i]; } sort(weight,weight+n); int cnt = 0; int left = 0; int right = n-1; while(left <= right) { if(weight[left] + weight[right] <= m) { left++; right--; cnt++; } else { right--; cnt++; } } cout<<cnt<<endl; return 0;}
新聞熱點
疑難解答