【题解】「UVA1149」装箱 Bin Packing

做法显然：贪心，但是怎么贪？

首先从大到小或从小到大排序，窝这次是从大到小排，这样更容易理解（从小到大更方变）
然后设置两个变量 front 和 after 作为前指针和后指针。
循环判断：
- 当前后两个数能放入背包时，则 ans++ 并把两指针：
```
front++;

after--;
```
- 当不能同时放入时，放进大的那个，也就是前面的那个，并且 ans++, front++;

最后看一下code：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int NR = 1e5 + 5;

int t, n, m, v[NR], front, after, ans;

bool cmp(int x, int y)

{

	return x > y;

}

void Initialization()//每组数据前后初始化

{

	memset(v, 0, sizeof(v));//清零

	n = 0;

	m = 0;

	front = 1;

	after = 0;

	ans = 0;

}

void Cin()//每组数据的输入

{

	cin >> n >> m;

		for (int i = 1; i <= n; i++)

			cin >> v[i];

	after = n;

}

int main()

{

	cin >> t;

	Initialization();//初始化

	for (int T = 1; T <= t; T++)

	{

		Cin();//输入

		sort(v + 1, v + n + 1, cmp);//排序

		for (int i = 1; i <= n; i++)//循环n次，因为最多分配n次，不会超过n次

			if (front >= after)//如果前指针已经超过或等于后指针时说明已经结束,所以结束循环

			{

				ans++;

				cout << ans << endl;//输出答案

				Initialization();//初始化

				break;

			}

			else if (v[front] + v[after] <= m)

			{//如果前后两个物品能放下

				ans++;

				front++;//前指针向后移

				after--;//后指针向前移

			}

			else

			{//否则的话

				ans++;

				front++;//只有前指针向后移

			}

	}

	return 0;

}

求赞ฅʕ•̫͡•ʔฅ

巴特西

【题解】「UVA1149」装箱 Bin Packing

最新文章

热门文章