ACM - CF - 1498B - Box Fitting - 数据结构+二分

题目链接

题意：
n个木条，高度为1，长度都是2的次幂。问给定长度为L的方格，高度为1，最少需要多少个这样的方格可以把所有n个木条放进去？

思路：
每次放可以放的最大的！即，贪心。
难点：
比较当前格子的剩余量以及剩下木条的可用的最大值时，需要排序。排好了之后，每次放进去的木条应该是最接近剩下长度的。

举例：
在样例1中，应该放：8+8，而不是8+4+2+1.

vector<int> 可以排序，怎么解决贪心的问题：二分。
upper_bound()：在有序数组中，找到用于在指定范围内查找大于目标值的第一个元素。
lower_bound()：在有序数组中，找到用于在指定范围内查找不小于（大于等于）目标值的第一个元素。
问题又来了：
题目中贪心要找的是小于等于啊！
我自己的小技巧是：把正数变成负数，扔进去。正数是小于等于，那么负数就是大于等于。</int>

一开始sort之后，数组就有序了。每次找到一个就拿走一个，数组仍然有序。

代码如下：

#include<bits/stdc++.h>
using namespace std;

vector<int> a;
vector<int>::iterator it;
int T;
int n, m, x;
int ans;

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);
    while(T--){
        if (a.size()) a.clear();
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++){
            scanf("%d", &x);
            a.push_back(x * (-1));
        }
        sort(a.begin(), a.end());
        //for(it=a.begin(); it!=a.end(); it++)
        //    cout<<*it<<" ";
        //cout << endl;
        ans = 0;
        while(a.size()){
            int Left = m * (-1);
            int flag = 0;
            while(!flag){
                it = lower_bound(a.begin(), a.end(), Left);
                if (it < a.end()){
                    Left -= (*it);
                    a.erase(it);
                }
                else{
                    flag = 1;
                }
            }
            ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}