Bin Packing-算是一个复杂度优化的好思想

Bin Packing

My Tags	(Edit)

	Source : SWERC 2005
	Time limit : 1 sec		Memory limit : 32 M

Submitted : 412, Accepted : 173

A set of n 1-dimensional items have to be packed in identical bins. All bins have exactly the samelength l and each item i has length l _i <= l. We look for a minimal number of bins q such that

• each bin contains at most 2 items,
• each item is packed in one of the q bins,
• the sum of the lengths of the items packed in a bin does not exceed l.

You are requested, given the integer values n, l, l₁, ..., l_n, to compute the optimal number of bins q.

InputThe first line of the input file contains the number of items n (1 <= n <= 10⁵). The second line containsone integer that corresponds to the bin length l <= 10000. We then have n lines containing one integervalue that represents the length of the items.

There are multiple test cases. Process to end of file.

Output

For each input file, your program has to write the minimal number of bins required to pack all items.

Sample Input

10
80
70
15
30
35
10
80
20
35
10
30

Sample Ouput

6

本题很明显的贪心，以前自己的码量不是很强，所以知道真么弄，也写不出来，把自己想到的能写出来是我做ACM的主要原因。此题很明显是先从大到小的排序，然后从开始往后少找到那个恰好与其和不大于L的放在一起，贪心的正确性很好证明，关键是降低复杂度。实际上很简单，就是与第一个能放到一起的箱子，第二个一定可以和它们放到一起，因此找个堆栈，实际上一个top就行了，在从后往前扫描的过程中不断的入队，下一次的起始点是上一次恰好之和大于L的地方，整体复杂度为：O(n);

#include <iostream>
#include <cstdio>
#include<algorithm>
#include <cstring>
using namespace std;
const int MAX = 100001;
int a[MAX];
int top;

bool cmp(const int &a, const int &b) {
    return a>b;
}

int get_result(int n, int L) {
    sort(a, a + n, cmp);
    top = 0;
    int size = 0;
    for (int i = 0, j = n - 1; i <= j; i++) {
        size++;
        while (a[i] + a[j] <= L && i < j) {
            top++;
            j--;
        }
        if (top > 0) top--;
    }
    size += (top + 1) / 2;
    return size;
}

int main() {
    int n, L;
    while (scanf("%d", &n) != EOF) {
        scanf("%d", &L);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        printf("%d\n", get_result(n, L));
    }
    return 0;
}