【题解】LuoGu3052：[USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper

原题传送门
题目描述

A little known fact about Bessie and friends is that they love stair climbing races. A better known fact is that cows really don’t like going down stairs. So after the cows finish racing to the top of their favorite skyscraper, they had a problem. Refusing to climb back down using the stairs, the cows are forced to use the elevator in order to get back to the ground floor.

The elevator has a maximum weight capacity of W (1 <= W <= 100,000,000) pounds and cow i weighs C_i (1 <= C_i <= W) pounds. Please help Bessie figure out how to get all the N (1 <= N <= 18) of the cows to the ground floor using the least number of elevator rides. The sum of the weights of the cows on each elevator ride must be no larger than W.

给出n个物品，体积为w[i]，现把其分成若干组，要求每组总体积<=W，问最小分组。(n<=18)

输入输出格式

输入格式：
* Line 1: N and W separated by a space.

• Lines 2..1+N: Line i+1 contains the integer C_i, giving the weight of one of the cows.

输出格式：
* A single integer, R, indicating the minimum number of elevator rides needed.

one of the R trips down the elevator.
输入样例
4 10
5
6
3
7
输出样例
3

【题解】
这题乍一看以为是裸的贪心，然后发现会wa掉。后来又想到弄全排列的暴力方法，发现n≤18，也不行。最后想到了状压。
可以先预处理出所有可以分成一组的方案，用二进制压缩，然后用贪心的思想，w加起来越接近W是越优的，所以来个快排然后再贪心搞定

Code：

var
    a:array[0..10000000] of record
        sum,num:longint;
    end;
    n,m,i,j,tot,sum,x,ans:longint;
    w:array[0..1000000] of longint;

procedure swap(var x,y:longint);
var
    tmp:longint;

begin
    tmp := x; x := y; y := tmp;
end;

procedure sort(l,r:longint);
var
    i,j,mid:longint;

begin
    i := l; j := r; mid := a[(l + r) >> 1].sum;
    repeat
        while a[i].sum > mid do inc(i);
        while a[j].sum < mid do dec(j);
        if i <= j then
        begin
            swap(a[i].sum,a[j].sum);
            swap(a[i].num,a[j].num);
            inc(i); dec(j);
        end;
    until i > j;
    if i < r then sort(i,r);
    if l < j then sort(l,j);
end;

begin
    readln(n,m);
    for i := 1 to n do readln(w[i]);
    for i := 0 to 1 << n - 1 do
    begin
        x := i;
        j := 1;
        sum := 0;
        while j <= n do
        begin
            if x and 1 <> 0 then inc(sum,w[j]);
            inc(j);
            x := x >> 1;
        end;
        if sum <= m then
        begin
            inc(tot);
            a[tot].num := i;
            a[tot].sum := sum;
        end;
    end;
    sort(1,tot);
    sum := 0;
    for i := 1 to tot do
    begin
        if sum and a[i].num = 0 then
        begin
            sum := sum or a[i].num;
            inc(ans);
        end;
        if sum = (1 << n - 1) then break;
    end;
    writeln(ans);
end.