建设企业网站公司南通网络推广

题目描述

有 nn 名学生骑双人自行车旅游，每辆双人车最多载两人，也可以只载一人，载两人时，乘客的体重之和不能超过一个给定的上限 tt。

已知学生的体重分别为 a1,a2,…,ana1​,a2​,…,an​。请如何安排才能让所有学生骑上车且使用的车辆达到最少。

输入格式

• 第一行，两个整数：nn 与 tt
• 第二行，nn 个整数 a1,a2,…,ana1​,a2​,…,an​

输出格式

• 单个整数，表示最少车辆数。

数据范围

• 对于 30%30% 的数据，1≤n≤101≤n≤10
• 对于 60%60% 的数据，1≤n≤1,0001≤n≤1,000
• 对于 100%100% 的数据，1≤n≤100,0001≤n≤100,000
• 1≤ai≤t≤1,000,0001≤ai​≤t≤1,000,000

样例数据

输入:

7 50
15 41 32 42 27 25 19

输出:

5

详见代码：

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int ans = 0;
int n;
int t;
int main() 
{scanf("%d%d", &n, &t);for (int i = 1; i <= n; i++){scanf("%d", &a[i]);}sort(a + 1, a + n + 1);int left = 1;int right = n;while (left < right) {if (a[left] + a[right] <= t) {ans++;left++;right--;} else{ans++;right--;}}if (right == left) ans++;cout << ans;return 0;
}