题目链接：http://poj.org/problem?id=2782
题目大意： 给出n袋长度不一定相同的垃圾，把它们全部装在长度不超过L的垃圾桶里；
每个垃圾桶至多有两袋垃圾，并且垃圾的长度相加小于L；
求最少用多少个垃圾桶可以装入全部垃圾；
解题思路： 每个垃圾桶最多只能有两袋垃圾，也就是说可以装是一袋或者两袋；
先排序，然后分别从最小、最大两个极端开始枚举：
如果相加小于或等于L，那么可以装下两袋垃圾，并且标记；
最后把只能装入一个垃圾桶的垃圾袋统计出来，和上面的相加！
代码：
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define MAX 100001
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
int n,l,a[MAX];
int main()
{
int i,j,k,temp;
scanf("%d%d",&n,&l);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n); //把桶的长度从小到大排列
temp=n-1;
for(i=0,k=0;i<n-1;i++)
{
for(j=temp;j>i;j--) //j=n-1 会TLE
{
if(a[i]!=-1&&a[j]!=-1&&a[i]+a[j]<=l) //如果这两包垃圾没塞进垃圾桶，并且两个的长度相加小于l
{
k++;
a[i]=-1; //使用之后标记
a[j]=-1; //使用之后标记
temp=j; //***这个很重要，记录最后一次塞过的那个桶，否则会超时
break;
}
}
}
for(i=0;i<n;i++)
{
if(a[i]!=-1)
k++;
}
printf("%d\n",k);
return 0;
}
注：原创文章，转载请注明出处.