CF798D.Mike and distribution
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Mike has always been thinking about the harshness of social inequality. He's so obsessed with it that sometimes it even affects him while solving problems. At the moment, Mike has two sequences of positive integers A = [_a_1, _a_2, ..., a__n] and B = [_b_1, _b_2, ..., b__n] of length n each which he uses to ask people some quite peculiar questions.
To test you on how good are you at spotting inequality in life, he wants you to find an "unfair" subset of the original sequence. To be more precise, he wants you to select k numbers P = [_p_1, _p_2, ..., p__k] such that 1 ≤ p__i ≤ n for 1 ≤ i ≤ k and elements in P are distinct. Sequence P will represent indices of elements that you'll select from both sequences. He calls such a subset P "unfair" if and only if the following conditions are satisfied: 2·(_a__p_1 + ... + a__p__k) is greater than the sum of all elements from sequence A, and 2·(_b__p_1 + ... + b__p__k) is greater than the sum of all elements from the sequence B. Also, k should be smaller or equal to
because it will be to easy to find sequence P if he allowed you to select too many elements!
Mike guarantees you that a solution will always exist given the conditions described above, so please help him satisfy his curiosity!
迈克一直在思考社会不平等的严酷性。他对这个问题如此着迷,以至于有时甚至在解题时也会受到影响。目前,迈克拥有两个长度均为 $ n $ 的正整数序列:$ A = [a_1, a_2, \dots, a_n] $ 和 $ B = [b_1, b_2, \dots, b_n] $,他常常用它们向别人提出一些非常奇特的问题。
为了测试你能否敏锐地察觉现实生活中的不平等现象,他希望你从原始序列中找出一个“不公平”的子集。更准确地说,他希望你选出 $ k $ 个下标 $ P = [p_1, p_2, \dots, p_k] $,满足对所有 $ 1 \le i \le k $,均有 $ 1 \le p_i \le n $,且 $ P $ 中的元素互不相同。序列 $ P $ 将表示你将从两个序列中选取元素所对应的下标。当且仅当满足以下条件时,他称这样的子集 $ P $ 为“不公平”的:
- $ 2 \cdot (a_{p_1} + \dots + a_{p_k}) $ 严格大于序列 $ A $ 中所有元素之和;
- $ 2 \cdot (b_{p_1} + \dots + b_{p_k}) $ 严格大于序列 $ B $ 中所有元素之和。
此外,$ k $ 必须满足 $ k \leq $
,因为若允许你选择过多元素,寻找序列 $ P $ 就会变得过于简单!
迈克向你保证,在上述条件下,解一定存在。请帮助他满足这份好奇心!
输入格式
The first line contains integer n (1 ≤ n ≤ 105) — the number of elements in the sequences.
On the second line there are n space-separated integers _a_1, ..., a__n (1 ≤ a__i ≤ 109) — elements of sequence A.
On the third line there are also n space-separated integers _b_1, ..., b__n (1 ≤ b__i ≤ 109) — elements of sequence B.
第一行包含一个整数 n(1≤n≤105)—— 序列中元素的个数。
第二行包含 n 个用空格分隔的整数 a1,…,an(1≤ai≤109)—— 序列 A 的元素。
第三行也包含 n 个用空格分隔的整数 b1,…,bn(1≤bi≤109)—— 序列 B 的元素。
输出格式
On the first line output an integer k which represents the size of the found subset. k should be less or equal to
.
On the next line print k integers _p_1, _p_2, ..., p__k (1 ≤ p__i ≤ n) — the elements of sequence P. You can print the numbers in any order you want. Elements in sequence P should be distinct.
第一行输出一个整数 k,表示所找到子集的大小。k 应满足 k≤2n。
接下来一行输出 k 个整数 p1, p2, …, pk(其中 1≤pi≤n)——即序列 P 的元素。你可以以任意顺序输出这些数字。序列 P 中的元素必须互不相同。
输入输出样例
输入#1
5 8 7 4 8 3 4 2 5 3 7
输出#1
3 1 4 5
输入解题思路,AI测评打分。不知道怎么写?