35 人解决,47 人已尝试。
43 份提交通过,共有 161 份提交。
4.6 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
oxx 与 xjj 终于到了 Xiamen,他们第一件事就是去吃当地著名的特产椰子饼。
他们共买了 $n$ 盒礼盒,第 $i$ 盒含 $a_i$ 块椰子饼。oxx 与 xjj 约定让 oxx 来分配这 $n$ 盒椰子饼。
为了讨好 xjj ,oxx 决定自己的椰子饼的总数要不大于 xjj 的总数。但是 oxx 知道贪吃的 xjj 会忍不住拆开一盒吃了,因此贪心的 oxx 希望: xjj 无论拆开哪一盒她自己的椰子饼后,oxx 拥有的椰子饼总数要不小于 xjj 剩余的椰子饼总数。oxx 想知道是否存在一个分配方案能够满足他的要求,如果存在输出 Yes
,并输出方案,否则 No
。
如果上述题意让你感到很困惑的话,我们要求的是 $S={a_1,a_2,\ldots,a_n}$ 这一多重集的一个非空子集 $S’={a_{i_1}, a_{i_2}, \ldots, a_{i_k} }$,使得 $$\left(Sum(S’) \le Sum(S-S’) \right) \land \left(\forall t \in S-S’, Sum(S’) \ge Sum(S-S’) - t\right) $$
记多重集 $Sum(A)$ 表示多重集 $A$ 所有元素的和。特别地,$Sum(\varnothing)=0$。
更困惑了吗?Here we go.
第一行一个整数 $n$ $(2 \leq n \leq 10^6)$。
接下去一行,$n$ 个整数 $a_1,a_2,\ldots,a_n$ $(1 \leq a_i \leq 10^6)$ 分别表示每盒椰子饼的个数。
第一行一个字符串,Yes
表示存在这样的方案,No
表示不存在。
若为 Yes
,第二行一个整数 $m$ ($1 \le m \le n - 1$),表示 oxx 自己选的椰子饼数量。
第三行 $m$ 个用空格隔开的整数,表示 oxx 所选取的椰子饼的编号,下标从 1 开始,编号不能有重复,顺序无所谓。
2 1 2
Yes 1 1
7 4 5 4 5 4 5 4
Yes 3 2 4 6
样例 2:在 oxx 挑了 5、5、5 这三个之后,总和 15 不超过 xjj 拿到的 4、4、4、4 的总和 16,而且无论 xjj 偷吃了哪个(反正都是 4),15 总大于等于 12。
35 人解决,47 人已尝试。
43 份提交通过,共有 161 份提交。
4.6 EMB 奖励。