B. Bin Packing Problem(线段树+multiset)

Problem - B - Codeforces

题意:

Lzw现在正在上运筹学的课。今天老师讲的是垃圾箱包装问题和一些解决该问题的近似算法。

在垃圾箱包装问题中，不同体积的物品必须以最小化所使用的垃圾箱数量的方式装入固定容量为C的有限数量的垃圾箱。在计算复杂性理论中，它是一个组合性的NP-hard问题。

有两种经典的近似算法。

第一种拟合算法。按输入顺序考虑项目，并维护一个最初为空的仓列表。在每一步中，它试图将当前项目放在列表中第一个可以容纳该项目的仓中。如果没有找到合适的仓，它就在列表的最后添加一个新的仓，并将项目放入新的仓中。
最佳适合算法。按输入顺序考虑项目，并保持一个仓的列表，最初为空。在每一步中，它都试图将当前的项目放入能够容纳该项目的最佳仓中。"最佳 "的意思是，如果有一个以上的仓可以容纳该物品，则选择剩余空间最小的仓。如果没有找到合适的垃圾箱，就会增加一个新的垃圾箱，然后将物品放入新的垃圾箱。
请帮助Lzw实现这两种算法，并找出每种算法将使用多少个仓。

输入
输入包含多个案例。输入的第一行包含一个正整数T，即案例的数量。

对于每个案例，输入的第一行包含两个整数n,C（1≤n≤106，1≤C≤109），即物品的数量和每个仓的容量。第二行包含n个整数，其中第i个（1≤i≤n）整数ai（1≤ai≤C）表示第i个物品的容量。

保证所有情况下的n之和不超过106。

输出
对于每个案例，打印一个包含两个整数的单行，分别表示第一次拟合和最佳拟合算法所使用的仓的数量。

例子
input
2
2 2
1 1
5 10
5 8 2 5 9
输出
1 1
4 3

题解:

第二种,我们每次要找剩余空间中最小的部分,可以用multiset来维护,二分查找第一个大于的,然后删去,添加,如果没有,在结尾添加(注意二分查找要用multiset自带的lower_bound)

二分找的是指针,所以删去时,可以直接删,如果插入就*p

第一种我们首先定义n个位置的容量为c,然后建树,得到每段最大的的值,然后每次根据a[i],更新,如果左子树最大值大于a[i],就往左找,否则往右找,找到后,记得更新ma[rt],与v[l]的值

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
int n,c;
int a[4000040];
int v[4000040];
int ma[4000040];
void pushup(int rt)
{
	ma[rt] = max(ma[rt*2],ma[rt*2+1]);
}
void builid(int rt,int l,int r)
{
	if(l == r)
	{
		ma [rt] = v[l];
		return ;
	}
	int mid = (l+r)/2;
	builid(rt*2,l,mid);
	builid(rt*2+1,mid+1,r);
	pushup(rt);
}
void change(int rt,int l,int r,int x)
{
	if(l == r)
	{
		ma[rt] -= x;
		v[l] -= x;
		return;
	}
	int mid = (l + r)/2;
	if(x <= ma[rt*2])
	{
		change(rt*2,l,mid,x);
	}
	else
	{
		change(rt*2+1,mid+1,r,x);
	}
	pushup(rt);
}
void solve()
{
	cin >> n >>c;
	multiset<int> ans;
	ans.insert(c);
	int cnt2 = 1;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	for(int i = 1;i <= n;i++)
	{
		auto p = ans.lower_bound(a[i]);
		if(p == ans.end())
		{
			cnt2++;
			ans.insert(c-a[i]);
		}
		else
		{
			ans.erase(p);
			ans.insert(*p-a[i]);
		}
	}
	for(int i = 1;i <= n;i++)
	v[i] = c;
	builid(1,1,n);
	int cnt1 = 0;
	for(int i = 1;i <= n;i++)
	{
		change(1,1,n,a[i]);
	}
	for(int i = 1;i <= n;i++)
	{
		if(v[i] != c)
		cnt1++;
		else
		break;
	}
	cout<<cnt1<<" "<<cnt2<<"\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
}