3496. 贪吃的 xjj 和贪心的 oxx

单点时限: 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 开始,编号不能有重复,顺序无所谓。

样例

Input
2
1 2
Output
Yes
1
1
Input
7
4 5 4 5 4 5 4
Output
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 奖励。

创建: 6 年,9 月前.

修改: 6 年,8 月前.

最后提交: 1 年,8 月前.

来源: EOJ Monthly 2018.2

题目标签