← 返回题目

题库练习求逆序对问题

← 上一题下一题 →

A71279 | $求逆序对问题$

来源编程题

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定 N 个数的序列 a_1,a_2, \dots ,a_N ，定义一个数对 (a_i, a_j) 为 “重要逆序对” 的充要条件为 i < j 且 a_i > 2 \times a_j。 求给定序列中“重要逆序对”的个数。

输入格式

本题有多个测试点，每个测试点分为两行： 第一行为序列中数字的个数 N（1 ≤ N ≤ 200000）； 第二行为序列 a_1, a_2, \dots , a_N (0 ≤a_i≤ 10000000 )，由空格分开。 N=0 表示输入结束。

输出格式

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

输入输出样例

输入 #1

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

输出 #1

C++ 编辑器

输入

输出