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

2023-10-28 07:30

本文主要是介绍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++;elsebreak;}cout<<cnt1<<" "<<cnt2<<"\n";
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--){solve();}
}

 

这篇关于B. Bin Packing Problem(线段树+multiset)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/291656

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

poj 1127 线段相交的判定

题意: 有n根木棍,每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连,当他们之间有公共点时,就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析: 线段相交的判定。 首先,模板中的线段相交是不判端点的,所以要加一个端点在直线上的判定; 然后,端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的,所以要加是否端点相等的判断。 最后

HDU4737线段树

题目大意:给定一系列数,F(i,j)表示对从ai到aj连续求或运算,(i<=j)求F(i,j)<=m的总数。 const int Max_N = 100008 ;int sum[Max_N<<2] , x[Max_N] ;int n , m ;void push_up(int t){sum[t] = sum[t<<1] | sum[t<<1|1] ;}void upd

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;