[蓝桥杯 2021 国 C] 巧克力

Luogu

IDLGP8769

Time1000ms

Memory128MB

DifficultyP4

贪心堆2021蓝桥杯国赛

小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，请问小蓝最少花多少钱能买到让自己吃 $x$ 天的巧克力。 ## Input 输入的第一行包含两个整数 $x$，$n$，分别表示需要吃巧克力的天数和巧克力的种类数。接下来 $n$ 行描述货架上的巧克力，其中第 $i$ 行包含三个整数 $a_i$，$b_i$，$c_i$，表示第 $i$ 种巧克力的单价为 $a_i$，保质期还剩 $b_i$ 天（从现在开始的 $b_i$ 天可以吃），数量为 $c_i$。 ## Output 输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 $x$ 天的购买方案，输出 $−1$。 [samples] ## Note **【样例说明】** 一种最佳的方案是第 $1$ 种买 $5$ 块，第 $2$ 种买 $2$ 块，第 $3$ 种买 $3$ 块。前 $5$ 天吃第 $1$ 种，第 $6$、$7$ 天吃第 $2$ 种，第 $8$ 至 $10$ 天吃第 $3$ 种。 **【评测用例规模与约定】** 对于 $30\%$ 的评测用例，$n,x \le 1000$。对于所有评测用例，$1\le n,x\le 10^5$，$1 ≤ a_i,b_i ,c_i\le10^9$。蓝桥杯 2021 国赛 C 组 I 题。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2021 国 C] 巧克力",
    "description": {
      "content": "小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。 一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，请问小蓝最少花多少钱能买到让自己吃 $x$ 天的巧克力。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8769"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。\n\n一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，请问小蓝最少花多少钱能买到让自己吃 $x$ 天的巧克力。\n\n## Input\n\n输入的第一行包含两个整数 $x$，$n$，分别表示需要吃巧克力的天数和巧克力的种类数。\n\n接下来 $n$ 行描述货架上的巧克力，其中第 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments