[ROIR 2023] 地铁建设 (Day 2)

Luogu

IDLGP10098

Time1000ms

Memory512MB

DifficultyP2

数学二分2023Special Judge枚举ROIR（俄罗斯）

最少需要提供多大的电压（电压需要是整数），才能使所有发动机的总功率大于或等于 $p$？ ## Input 第一行输入两个整数 $n$ 和 $p$。接下来的 $n$ 行，每行包含三个整数 $z_i,a_i,b_i$。 ## Output 输出一个整数表示最小电压。 [samples] ## Background 翻译自 [ROIR 2023 D2T1](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。用于铺设地铁隧道的盾构机有 $n$ 个发动机。所有发动机是并联的，所以所有发动机两端的电压都相同。每个发动机有两种模式，假设所有发动机接收到的电压都为 $x$，则当 $x\le z_i$ 时第 $i$ 个发动机在第一模式下工作，否则它在第二模式下工作。第 $i$ 个发动机在第一模式下的单位电流为 $a_i$，在第二模式下的单位电流为 $b_i$。所以，根据 $P=UI$，当发动机处于第一模式时，每增加 $1$ 单位电压，其功率增加 $a_i$ 单位；当发动机处于第二模式时，每增加 $1$ 单位电压，其功率增加 $b_i$ 单位。换句话说，当电压为 $x$ 单位电压，如果第 $i$ 个发动机处于第一模式下，它以 $a_i\times x$ 的单位功率运行；如果处于第二模式下，它以 $a_i\times z_i + b_i\times(x - z_i)$ 的单位功率运行。 ## Note 本题使用捆绑测试。 | 子任务编号 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $20$ | $n=1$ | | $2$ | $20$ | $a_i,b_i\le100,p\le10^5$ | | $3$ | $20$ | 所有 $z_i$ 均相等 | | $4$ | $20$ | $n\le2$ | | $5$ | $20$ | | 对于 $100\%$ 的数据，$1 \le n \le 100,1 \le p \le 10^{12},1 \le z_i \le 10^9,1 \le a_i,b_i \le 10^4$。

Samples

Input #1

1 6
4 1 2

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[ROIR 2023] 地铁建设 (Day 2)",
    "description": {
      "content": "最少需要提供多大的电压（电压需要是整数），才能使所有发动机的总功率大于或等于 $p$？",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10098"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "最少需要提供多大的电压（电压需要是整数），才能使所有发动机的总功率大于或等于 $p$？\n\n## Input\n\n第一行输入两个整数 $n$ 和 $p$。\n\n接下来的 $n$ 行，每行包含三个整数 $z_i,a_i,b_i$。\n\n## Output\n\n输出一个整数表示最小电压。\n\n[samples]\n\n## Background\n\n翻译自 [ROIR 2023 D2T1](https://neerc....",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments