UVA1149 装箱 Bin Packing

UVA1149 装箱 Bin Packing

知识点：贪心，乘船问题

比较简单的贪心，题目应该是保证有结果的，从双向开始扫描一遍即可

#include 

#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long ll;
typedef vector vi;
typedef pair pa;

const int N = 1e5 + 5;

int a[N];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, l;
        cin >> n >> l;
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
        int p1 = 0, p2 = n - 1;
        int cnt = 0;
        while (p1 <= p2) {
            if (p1 == p2) { cnt++; break; }
            if (a[p1] + a[p2] > l) { p2--; cnt++; }
            else { p2--; p1++; cnt++; }
        }
        cout << cnt << endl;
        if (t) cout << endl;
    }
    return 0;
}