AT_abc388_e.[ABC388E] Simultaneous Kagamimochi

普及+/提高

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

有 NN 个大小不一的饼。第 ii 个饼的大小为 aia_i(1≤i≤N1 \le i \le N)。

对于任意两个大小分别为 aa 和 bb 的饼 AA 和 BB,如果 aa 小于或等于 bb 的一半,即 a≤b2a\le \frac{b}{2},则可以将饼 AA 放在饼 BB 上制作一个“镜饼”。

从 NN 个饼中任选两个,使得其中一个饼放在另一个饼上制作一个“镜饼”。

需要求出可以同时制作多少种不同的“镜饼”。

Translate by chinazhanghaoxun。

输入格式

输入将以以下格式通过标准输入给出:

N A1 A2 … ANN \ A_1\ A_2\ \dots\ A_N

输出格式

输出可以制作的镜饼数。

数据限制

  • 2≤N≤5×1052\le N\le 5\times 10^5
  • 1≤Ai≤109(1≤i≤N)1\le A_i \le 10^9(1\le i\le N)
  • Ai≤Ai+1(1≤i≤N)A_i\le A_{i+1}(1\le i\le N)
  • 输入值均为整数

输入输出样例

  • 输入#1

    6
    2 3 4 4 7 10

    输出#1

    3
  • 输入#2

    3
    387 388 389

    输出#2

    0
  • 输入#3

    24
    307 321 330 339 349 392 422 430 477 481 488 537 541 571 575 602 614 660 669 678 712 723 785 792

    输出#3

    6

输入解题思路,AI测评打分。不知道怎么写?

首页