Description
PIPI参加志愿者活动去沙滩上捡垃圾，已知沙滩上有 N 堆垃圾，每个垃圾的重量为 L，PIPI的垃圾袋容量为 M，一个垃圾袋最多能装两个垃圾。问: PIPI最少需要多少个垃圾袋才能把垃圾全带走？
Input
第一行包含一个正整数T代表测试样例组数。
对于每组测试用例，第一行包含两个正整数 N和 M(N<=105,M<=109)。
第二行包含 N 个正整数代表每一个垃圾的重量L。
Output
对于每组样例，输出包含一个正整数代表最少需要的垃圾袋数目。除了最后一组样例，每两组样例间有一个空行。
Sample Input
1
32
12 2
Sample Output
3
参考程序
#include <stdio.h>
#include <algorithm>
#define LEN 100000
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
long long gar[LEN],cnt=0,N,M,i,j;
scanf("%lld%lld",&N,&M);
for(i=0;i<N;i++)
{
scanf("%lld",&gar[i]);
}
sort(gar,gar+N);
i=0,j=N-1;
while(i<=j)
{
if(i==j)
{
cnt++;
break;
}
if(gar[i]+gar[j]<=M)
{
cnt++;
i++;
j--;
}
else
{
cnt++;
j--;
}
}
printf("%d\n",cnt);
if(T)
{
printf("\n");
}
}
return 0;
}
本题使用了C++中的数组排序函数sort()，但主体还是使用C语言实现。本题使用贪心设计策略，首先将垃圾重量从小到大进行排序，初始化i=0，j=N-1。
- 当gar[i]+gar[j]>M时，此时只能让gar[j]放在一个袋子里；
- 当gar[i]+gar[j]≤M时，此时可以将gar[i]、gar[j]一起放在一个袋子里；
- 最后如果只剩下一件垃圾，即i==j时，需要让gar[i]单独放在一个袋子里。
本题需要考虑大规模数据（数据大、数据量大）！
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: