#3711. 石子合并

石子合并

题目描述

石子合并

小张有一排 $$nn$$ 个石子,第 $$ii$$ 个石子位于位置 $$ii$$,石子的初始质量均为正整数,小张记录了这些石子的初始总质量 $$vv$$。

小张可以进行两种操作:

  1. 合并连续的两堆石子,用以表示的操作符号为 ‘+’,即对于两个相邻的石子 $$ii$$ 和 $$i+1i+1$$,将它们合并成一颗石子 $$ii$$,新石子的质量为其质量的和,即第 $$ii$$ 个石子的质量等于被合并的两颗石子的质量和。
  2. 分裂一颗石子为两堆石子,用以表示的操作符号为 ‘-’,即对于一个石子 $$ii$$,将其分裂成两颗石子 $$ii$$ 和 $$i+1i+1$$,新产生的两颗石子的质量各半,即第 $$ii$$ 个石子的质量等于原来石子质量的一半,第 $$i+1i+1$$ 个石子的质量也等于原来石子质量的一半。

小张发现在某些情况下,通过上述两种操作的使用,可以改变石子的排列顺序和质量分布,但总质量保持不变。

他想请你计算出,对于初始总质量为 $$vv$$ 以及初始位置上的石子质量分布情况, 通过上述两种操作能否将石子重新排列成质量分布如目标质量数组 $$w=[w1,w2,…,wn]w=[w_1,w_2, \ldots,w_n]$$ 中的任意一种。

格式

输入格式

每组测试数据占据一行内,包含用空格隔开的两个整数 $$nn$$, $$vv$$,($$1≤n≤1001 \leq n \leq 100$$, $$1≤v≤1051 \leq v\leq 10^5$$) —— 分别表示石子的初始数量以及初始总质量。

接下一行包含 $$nn$$ 用空格隔开的整数 $$a1,a2,…,ana_1,a_2, \ldots,a_n$$,($$1≤ai≤v1 \leq a_i \leq v$$) —— 表示初始石子质量分布情况,显然有 $$a1+a2+…+an=va_1+a_2+ \ldots+a_n=v$$。

输出格式

请输出一行一个大写字母 ‘Y’ 或者 ‘N’,表示小张是否能够完成任务。

例:

对于初始的石子质量分布为 $$a=[1,2,3,4,5,6,7,8,9,10]a=[1,2,3,4,5,6,7,8,9,10]$$,初始总和 $$v=55v=55$$,通过两种操作可以使石子的质量分布成为 $$w=[5,4,1,6,2,10,3,9,8,7]w=[5,4,1,6,2,10,3,9,8,7]$$。

示例

10 55
1 2 3 4 5 6 7 8 9 10
Y

提示

本题拥有不绑定示例通过的通过点,调测数据拥有与正式数据相同的答案分布,请充分调测。

小张可以发现,初始的石子质量分布为 $$a=[1,2,3,4,5,6,7,8,9,10]a=[1,2,3,4,5,6,7,8,9,10]$$,初始总和 $$v=55v=55$$,通过两种操作可以使石子的质量分布成为 $$w=[5,4,1,6,2,10,3,9,8,7]w=[5,4,1,6,2,10,3,9,8,7]$$。

由于初始的石子在位置 $$i=6i=6$$ 的石子质量即为 6,在第一次操作中,我们可以将其分裂成两颗质量均为 3 的石子,分裂点位于该石子与它后面的石子之间,得到 $$[1,2,3,4,5,3,3,8,9,10][1,2,3,4,5,3,3,8,9,10]$$;由于初始的石子在位置 $$i=7i=7$$ 的石子质量即为7,在第一次操作中,我们可以将其分裂成两颗质量均为 $$3123\frac{1}{2}$$ 的石子,分裂点位于该石子与它后面的石子之间,得到 $$[1,2,3,4,5,3,3,4,9,10][1,2,3,4,5,3,3,4,9,10]$$。由于初始的石子在位置 $$i=8i=8$$ 的石子质量即为 $$88$$,在第一次操作中,我们可以将其分裂成两颗质量均为 4 的石子,分裂点位于该石子与它后面的石子之间,得到 $$[1,2,3,4,5,3,3,4,4,5][1,2,3,4,5,3,3,4,4,5]$$。由于初始的石子在位置 $$i=5i=5$$ 的石子质量即为 5,在第一次操作中,我们可以将其分裂成两颗质量均为 2.5 的石子,分裂点位于该石子与它后面的石子之间,得到 $$[1,2,3,4,2,5,3,4,4,5][1,2,3,4,2,5,3,4,4,5]$$。由于初始的石子在位置 $$i=6i=6$$ 的石子质量即为 3,在第一次操作中,我们可以将其分裂成两颗质量均为 1.5 的石子,分裂点位于该石子与它后面的石子之间,得到 $$[1,2,3,4,2,2,5,4,4,5][1,2,3,4,2,2,5,4,4,5]$$。由于初始的石子在位置 $$i=3i=3$$ 的石子质量即为 4,在第一次操作中,我们可以将其分裂成两颗质量均为 2 的石子,分裂点位于该石子与它后面的石子之间,得到 $$[1,2,2,3,2,2,5,4,4,5][1,2,2,3,2,2,5,4,4,5]$$。由于初始的石子在位置 $$i=10i=10$$ 的石子质量即为 5,在第一次操作中,我们可以将其分裂成两颗质量均为 2.5 的石子,分裂点位于该石子与它后面的石子之间,得到 $$[1,2,2,3,2,2,5,4,4,2,5][1,2,2,3,2,2,5,4,4,2,5]$$。由于初始的石子在位置 $$i=7i=7$$ 的石子质量即为 5,在第一次操作中,我们可以将其分裂成两颗质量均为 2.5 的石子,分裂点位于该石子与它后面的石子之间,得到 $$[1,2,2,3,2,2,2,5,4,2,5][1,2,2,3,2,2,2,5,4,2,5]$$。由于初始的石子在位置 $$i=8i=8$$ 的石子质量即为 4,在第一次操作中,我们可以将其分裂成两颗质量均为 2 的石子,分裂点位于该石子与它后面的石子之间,得到 $$[1,2,2,3,2,2,2,2,5,2,5][1,2,2,3,2,2,2,2,5,2,5]$$。由于初始的石子在位置 $$i=9i=9$$ 的石子质量即为 2,在第一次操作中,我们可以将其分裂成两颗质量均为 1 的石子,分裂点位于该石子与它后面的石子之间,得到 $$[1,2,2,3,2,2,2,2,1,5,2,5][1,2,2,3,2,2,2,2,1,5,2,5]$$。由于初始的石子在位置 $$i=10i=10$$ 的石子质量即为 5,在第一次操作中,我们可以将其分裂成两颗质量均为 2.5 的石子,分裂点位于该石子与它后面的石子之间,得到 $$[1,2,2,3,2,2,2,2,1,2,2,5][1,2,2,3,2,2,2,2,1,2,2,5]$$。由于初始的石子在位置 $$i=12i=12$$ 的石子质量即为 5,在第一次操作中,我们可以将其分裂成两颗质量均为 2.5 的石子,分裂点位于该石子与它后面的石子之间,得到 $$[1,2,2,3,2,2,2,2,1,2,2,2,2][1,2,2,3,2,2,2,2,1,2,2,2,2]$$。通过上述的多次操作,小张成功地将石子 rearrange 成了所需的质量分布。

样例

10 55
1 2 3 4 5 6 7 8 9 10
N 
3 3
1 1 1
N 

解析

石子合并

解题思路

这个问题要求我们判断是否可以通过合并和分裂石子的操作,将初始的石子质量分布 rearrange 成目标分布。需要注意的是,这些操作并不会改变石子的总质量,但可以改变石子的排列顺序。

首先,我们需要了解每个操作的效果。合并操作‘+’会将两个相邻的石子合并成一个,新石子的质量是原来的和。分裂操作‘-’会将一个石子分裂成两个,每个的新质量是一半。

然而,这些操作的进行并不是任意的。比如,要合并的两个石子必须是相邻的,而分裂的石子也不能随意分裂。那么,什么样的初始分布可以重排成目标分布呢?\n 经过分析,可以发现这个问题的关键在于,每个石子的质量在某些情况下可以被分割和合并,但必须满足一些条件。比如,当两个石子在目标中是相邻的,但初始时不是相邻的,那么就需要通过分裂和合并来实现。但是,分裂和合并的顺序可能会影响到是否能达成目标。

算法选择理由

为了解决这个问题,我们可以使用一种称为‘分数加法’的方法。具体来说,每个石子在初始和目标中的质量必须能够通过一系列的分裂和合并操作得到。分裂和合并可以看作是对某些分数的分解和组合。例如,当需要将一个质量为 x 的石子分裂成两个质量之和为 x 的分数时,可能需要满足一些 2 的幂次方的关系,因为每次分裂都会将质量除以 2。

然而,在这个具体问题中,正确的做法是使用一种贪心的堆方法。我们将每个石子视为一个节点,这些节点可以合并或分裂。通过维护一个优先队列,每次都处理当前质量不匹配的相邻石子对,直到所有石子的质量都相等为止。如果最终所有石子都能达到目标质量,则输出 'Y',否则输出 'N'。

复杂度分析

本算法的时间复杂度主要由优先队列的操作决定。在最坏情况下,每个操作都会进行 O(n log n) 的时间。由于 n 的最大值为 100,所以整个算法在数据规模上是完全可以接受的。

代码解释

代码中,我们使用了一个 Node 结构体来表示当前的石子段,包括左右边界。通过重载运算符 <,我们可以方便地在优先队列中对这些节点进行排序,确保每次处理质量不匹配的段。在 check 函数中,我们首先将所有不匹配的单个石子放入堆中,然后不断合并最重的两个段,直到堆中只剩下一个段。在每次合并时,我们会检查是否能在合并后得到目标质量,否则直接返回 false。如果最终的平均质量等于目标中的某个值,则返回 true。

这个方法能有效地模拟出通过分裂和合并操作达到目标分布的过程。需要注意的是,由于浮点数精度问题,在实际代码中使用了 1e-6 的容差进行比较。

来源

AI 生成 · olympiccoder:7b · 普及+/提高- · 动态规划