弹珠-题解
原题链接:Link
题目描述
有六种不同价值的弹珠,告诉你每一种有多少个,求能不能将弹珠均分为相等的两份。
输入格式给的很费解,其实就是给出了价值分别为 \(1 \sim 6\) 的弹珠的个数,此外输出格式里还要求多打一个空行,就坑的离谱。
思路分析
很容易想到的特判:如果总价值是奇数,直接输出 Can't be divided.
然后就很关键了,题目可以理解为:在所有珍珠中选出一些,使得价值和正好是总价值的一半。
怎么实现这个算法呢?
在一堆东西里面选出一些,使得总价值满足一定条件,很容易可以想到背包问题。
(如果没有学习过背包的,建议移步AcWing背包九讲(主题库2~10题)或者P1048)。
以下默认各位大佬都会01背包。
我们可以把珍珠的价值也看做费用,求在价值和不超过总价值的一半的前提下能够选的的最大价值,如果这个最大价值就是总价值的一半,那么可以均分,否则不行。
所以这个问题就可以转化为:
一共有6种弹珠,每种弹珠可能有多种,在价值和不超过总价值的一半的前提下求出能够选的的最大价值。
各位大佬肯定一眼就看出来这是一个多重背包问题。
多重背包
多重背包问题可以转化为01背包问题求解,最朴素的方法就是把一种当中的 \(n\) 个看成 \(n\) 个不同的物品,然后每个物品都可以取或者不取。也就是在经过如下操作后套用01背包模板:1
2
3
4
5
6
7
8
9int a[maxn]; //存储价值
int j = 1;
for (int i = 1; i <= 6; i++) {
int t;
cin >> t;
while (t--) {
a[j++] = i;
}
}
所以我们要进行优化。观察上面的步骤,让时间复杂度剧增的就是把一种当中的 \(n\) 个看成 \(n\) 个不同的物品,由于每一种物品都可能有很多个,所以最终的物品总数会很大。我们可以在这个方面着手优化:
我们的最终目的是使得分出来的物品可以表示 \(1 \sim n\) 里面的所有价值,为了达成这一目的,我们并不需要分出 \(n\) 个物体。
二进制优化
在计算机中,为了表示 \(1 \sim x\) ,我们只需要 \(\log_2 x\) 个bit。同样的道理,为了表示 \(1 \sim n\) 的所有数,我们只需把 \(n\) 拆分成 \(\log_2 n\) 个数。举个例子,对于 \(n = 30\) 我们可以拆成 \(1, 2, 4, 8, 15\) ,各位大佬可以自己试验亿下,一定可以表示 \(1 \sim 30\) 中的所有数。
根据这个原理,我们可以更改上述代码:1
2
3
4
5
6
7
8
9
10
11
12int j = 1;
for (int i = 1; i <= 6; i++) {
int t;
cin >> t;
int k = 1;
while (k <= t) {
a[j++] = k * i;
t -= k;
k <<= 1;
}
if (t > 0) a[j++] = t * i;
}
效率:https://www.luogu.com.cn/record/59760585。
AC代码
1 |
|