[GDKOI2024 普及组] 刷野 I

Luogu
IDLGP10072
Time1000ms
Memory512MB
DifficultyP4
2024广东O2优化
Zayin 是一个与怪物战斗的巫师,这次他将面临 $n$ 个站成一排的怪物,其中第 $i$ 个怪物的生命值是 $a_i$。 Zayin 率先使用一种攻击方式攻击,攻击过后所有血量小于等于 $0$ 的怪物死亡。在 Zayin 攻击一次后,所有存活的怪物对 Zayin 造成 $1$ 点伤害。以上步骤不断循环,直到 Zayin 击杀所有怪物为止。 Zayin 一共有三种攻击方式: - 普通攻击: 消耗 $0$ 点能量值,选择一只怪物并使其血量减少一点。 - 天音波: 消耗 $1$ 点能量值,选择一只怪物并使其血量减少两点。 - 天雷破: 消耗 $1$ 点能量值,使所有怪物血量减少一点。 现在 Zayin 一共有 $m$ 点能量,现在他想知道在最优的策略下,击败 $n$ 只怪物所损失的最少血量。 ## Input 输入的第一行包含两个正整数 $n, m(1 \leq n, m \leq 10^5)$,$n$ 表示怪物的个数,$m$ 表示 Zayin 拥有的能量值。 输入的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n(1 \leq a_i \leq 10^9)$,$a_i$ 表示第 $i$ 只怪物的血量。 ## Output 一行一个整数表示答案。 [samples] ## Note 对于 $30\%$ 的数据,$1 \leq n, m \leq 5$。 对于另外 $15\%$ 的数据,$m = 0$。 对于另外 $15\%$ 的数据,所有 $a_i$ 全部相等。 对于 $100\%$ 的数据,$1 \leq n \leq 10^5$,$0 \leq m \leq 10^5$,$1 \leq a_i \leq 10^9$。
Samples
Input #1
3 4
2 4 4
Output #1
6
API Response (JSON)
{
  "problem": {
    "name": "[GDKOI2024 普及组] 刷野 I",
    "description": {
      "content": "Zayin 是一个与怪物战斗的巫师,这次他将面临 $n$ 个站成一排的怪物,其中第 $i$ 个怪物的生命值是 $a_i$。 Zayin 率先使用一种攻击方式攻击,攻击过后所有血量小于等于 $0$ 的怪物死亡。在 Zayin 攻击一次后,所有存活的怪物对 Zayin 造成 $1$ 点伤害。以上步骤不断循环,直到 Zayin 击杀所有怪物为止。 Zayin 一共有三种攻击方式: - 普通攻击: ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10072"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Zayin 是一个与怪物战斗的巫师,这次他将面临 $n$ 个站成一排的怪物,其中第 $i$ 个怪物的生命值是 $a_i$。\n\nZayin 率先使用一种攻击方式攻击,攻击过后所有血量小于等于 $0$ 的怪物死亡。在 Zayin 攻击一次后,所有存活的怪物对 Zayin 造成 $1$ 点伤害。以上步骤不断循环,直到 Zayin 击杀所有怪物为止。\n\nZayin 一共有三种攻击方式:\n\n- 普通攻击: ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments