求逆序对问题

va587486 程序题 共 个子题

给定N个数的序列a1,a2,...aN，定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。

输入格式

本题有多个测试点，每个测试点分为两行：第一行为序列中数字的个数N（1 ≤ N ≤ 200000），第二行为序列a1, a2 ... aN(0 ≤ a ≤ 10000000)，由空格分开。N=0表示输入结束。

输出格式

每个测试点一行，输出一个整数，为给序列中“重要逆序对”的个数。

输入样例

10
0 9 8 7 6 5 4 3 2 1
0

输出样例

16

说明/提示

请注意答案范围，如果使用printf输出long long类型，请用%lld

限制

时间限制：1000，内存限制：256000

本题为编程题，提交代码并运行通过测试点后判分。

正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答，单题练习暂不支持
答案解析
提交记录
共 条 仅展示自由练习提交
正在加载提交记录…
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论，来发表第一条吧