E3-A 小水獭和蓝园

题目描述

小水獭正在浏览沙河校区的蓝园（BlueGraden）（Blue Graden）。

小水獭想将蓝园中 $n $朵花发往学院路，这 $n $朵花的重量分别为 a1,a2,…,ana_1,a_2,…,a_n，一个快递可以运送任意一朵花，或运送两朵重量之和不超过 mm 的花。

小水獭想知道，它最少需要发几个快递才能将所有的花发往学院路，你能帮帮它嘛？

输入格式

第一行一个正整数 t（1≤t≤10）t（1≤t≤10），表示数据组数。

对于每组数据，第一行两个正整数 n,m（1≤n≤105，1≤m≤109）n,m（1≤n≤10^5，1≤m≤10^9），含义同题目描述。

第二行 $n $个整数 a1,a2,…,an（1≤ai≤m）a_1,a_2,…,a_n（1≤a_i≤m），含义同题目描述。

输出格式

对于每组数据，输出一行一个正整数，表示最少需要的快递数量。

输入样例

1
2
3
4
5
2
5 5
1 2 3 4 5
2 3
2 2

输出样例

1
2
3
2

样例解释

第一组数据中，一种最优方案为 [1,4],[2,3],[5]。

第二组数据中，一种最优方案为 [1],[2]。

题目分析

一个快递最多只能运送两朵花，对于重量最大的花，如果它加上重量最轻的花超过mm那么就不再可能有其他花可以与他一起运送，此时选择单独运送最大的花，包裹数量加一，删除此花。如果没有超过mm那就可以选择这两朵花，此时将包裹数量加一，删除这两朵花再继续判断。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        deque<int> dq;
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < n; i++)
        {
            int x;
            cin >> x;
            dq.push_back(x);
        }
        sort(dq.begin(), dq.end());
        int ans = 0;
        while(dq.size()>0)
        {
            if(dq.size()==1)
            {
                ans++;
                break;
            }
            int a = dq.back();
            int b = dq.front();
            if(a+b>m)
            {
                ans++;
                dq.pop_back();
            }
            else
            {
                ans++;
                dq.pop_back();
                dq.pop_front();
            }
        }
        cout << ans << endl;
    }

    return 0;
}