#P12642. [KOI 2024 Round 1] 加倍

[KOI 2024 Round 1] 加倍

题目背景

试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

给定一个长度为 NN 的正整数序列 A1,A2,,ANA_1, A_2, \dots, A_N。现在希望将该序列变为升序排列。所谓升序排列,是指对于所有的 ii1iN11 \leq i \leq N - 1),都有 AiAi+1A_i \leq A_{i+1}

为了将序列 AA 排成升序,可以对序列执行以下操作若干次(可为零次):

  • 对于某个 ii1iN1 \leq i \leq N),将 AiA_i 乘以 22

你的任务是以最小的操作次数将序列 AA 排成升序,并输出所需的最小操作次数。

输入格式

第一行输入一个整数 NN
第二行输入 NN 个整数,表示 A1,A2,,ANA_1, A_2, \dots, A_N,以空格分隔。

输出格式

输出一个整数,表示将序列变为升序所需的最小操作次数。

5
3 1 4 1 5
4
5
3 1 5 1 5
6
5
1 2 3 4 5
0

提示

样例 1 说明

A2A_2A4A_4 各执行两次操作后,序列变为 [3,4,4,4,5][3, 4, 4, 4, 5]

样例 2 说明

A2A_2 操作两次,A4A_4 操作三次,A5A_5 操作一次,最终序列为 [3,4,5,8,10][3, 4, 5, 8, 10]

约束条件

  • 所有给定的数均为整数。
  • 1N2500001 \leq N \leq 250\,000
  • 1Ai10000001 \leq A_i \leq 1\,000\,000,其中 1iN1 \leq i \leq N

子问题

  1. (12 分)对于所有 ii1iN1 \leq i \leq N),Ai=1A_i = 1Ai=2A_i = 2
  2. (10 分)对于所有 ii1iN1 \leq i \leq N),存在非负整数 kik_i,使得 Ai=2kiA_i = 2^{k_i}
  3. (11 分)N10N \leq 10
  4. (19 分)对于所有 ii1iN1 \leq i \leq N),Ai=2A_i = 2Ai=3A_i = 3
  5. (20 分)对于所有 ii1iN11 \leq i \leq N - 1),AiAi+1A_i \geq A_{i+1}
  6. (28 分)无额外限制条件

翻译由 ChatGPT-4o 完成