[GDKOI2024 普及组] 刷野 II

Luogu

IDLGP10073

Time2000ms

Memory512MB

DifficultyP3

2024广东Special JudgeO2优化

Zayin 是一个与怪物战斗的巫师，这次他将面临 $n$ 个站成一排的怪物，其中第 $i$ 个怪物的生命值是 $a_i$。 Zayin 知道许多被压制的咒语，在这场战斗中，他决定使用一个名为” 闪电连击” 的咒语来一口气击败所有的怪物。让我们看看这个咒语是如何工作的。 - 首先，Zayin 选择一个怪物 $i(1 \leq i \leq n)$ 以及咒语的初始力量 $x$。 - 然后这个咒语会首先击中怪物 $i$，随后对于除第一个目标怪物外，Zayin 可以选择一个没有被该咒语击中过，并且与其中一个已经被击中的怪物相邻的怪物。 - 第一个被击中的目标怪物会受到 $x$ 的伤害，第二个目标怪物会受到 $x-1$ 的伤害，第三个受到 $x-2$ 的伤害，以此类推。不难看出，每个怪物都会被击中恰好一次。如果一个怪物受到的伤害不低于其生命值，则视为死亡。 Zayin 想展示他作为一个高级巫师的能力，所以他希望在只使用一次咒语就能杀死所有怪物的前提下，使用最少的初始力量 $x$。现在你需要求出所需的最少的初始力量，并给出一个方案。如果有多个不同的方案，只需要给出任意一个就可以了。 ## Input 第一行包含两个整数 $d, n$，表示测试点编号和怪物数。接下来一行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个怪物的血量。 ## Output 第一行输出一个整数 $x$，表示最少的初始力量。接下来第二行输出 $n$ 个用空格分割的下标 $monster_i(1 \leq i \leq n)$，其中 $monster_i$ 表示第 $i$ 个击中的目标怪物。 [samples] ## Note 对于所有测试数据，保证 $1 \leq n \leq 5 \times 10^6$ ，$1 \leq a_i \leq 10^9$。 | 测试点编号 | $n\leq$ | | :----------: | :----------: | | $1$ | $10$ | | $2$ | $20$ | | $3$ | $500$ | | $4$ | $5000$ | | $5$ | $5\times 10^4$ | | $6,7$ | $5\times 10^5$ | | $8,9,10$ | $5\times 10^6$ |

Samples

Input #1

1 10
19 9 12 5 10 7 16 15 17 12

Output #1

25
1 2 3 4 5 6 7 8 9 10

API Response (JSON)

{
  "problem": {
    "name": "[GDKOI2024 普及组] 刷野 II",
    "description": {
      "content": "Zayin 是一个与怪物战斗的巫师，这次他将面临 $n$ 个站成一排的怪物，其中第 $i$ 个怪物的生命值是 $a_i$。 Zayin 知道许多被压制的咒语，在这场战斗中，他决定使用一个名为” 闪电连击” 的咒语来一口气击败所有的怪物。让我们看看这个咒语是如何工作的。 - 首先，Zayin 选择一个怪物 $i(1 \\leq i \\leq n)$ 以及咒语的初始力量 $x$。 - 然后这个咒语会",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10073"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Zayin 是一个与怪物战斗的巫师，这次他将面临 $n$ 个站成一排的怪物，其中第 $i$ 个怪物的生命值是 $a_i$。\n\nZayin 知道许多被压制的咒语，在这场战斗中，他决定使用一个名为” 闪电连击” 的咒语来一口气击败所有的怪物。让我们看看这个咒语是如何工作的。\n\n- 首先，Zayin 选择一个怪物 $i(1 \\leq i \\leq n)$ 以及咒语的初始力量 $x$。\n- 然后这个咒语会...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments