[CSP-X2022 山东] 动物园

Luogu

IDLGB4098

Time1000ms

Memory512MB

DifficultyP3

2022山东CSP-X 小学组

某动物园里有 $n$ 个场馆和 $m$ 种动物（$m ≤ n$）。 $n$ 个场馆的编号分别用 $1,2,3, . . , n$ 表示；$m$ 种动物的编号分别用 $1,2,3, . . , m$ 表示。每一个场馆中只饲养了一只动物，不同的场馆可能饲养着相同种类的动物。这个动物园的门票比较特殊，游客在购买门票时必须说明要参观的场馆的起止编号 $a$ 和 $b$（起止编号会打印到游客购买的门票上），代表游客只能参观动物园的第 $a$ 个场馆至第 $b$ 个场馆（包含 $a,b$）里的动物，其他的场馆不能去。门票按一个场馆十元收费。如果你购买的门票的起止场馆编号是 $3$ 到 $8$，那么你需要花 $60$ 元钱购买门票，只能观看$3,4,5,6,7,8$ 号场馆的动物。小明希望看到动物园内所有种类的动物，同时小明是个非常节约的孩子，他希望花最少的钱买门票。请你帮小明计算：他最少需要花费多少钱买门票才能看到所有种类的动物（同一种动物他可能不止看一个）。注意：小明只能买一张门票。 ## Input 第一行两个整数 $n,m$，分别表示动物园内的场馆数量及动物种类数量。第二行是 $x_1,x_2,\cdots,x_n$，其中 $x_i$ 表示第 $i$ 个场馆中的动物种类编号。 ## Output 一行一个整数 $p$，表示小明的门票费用。 [samples] ## Note 对于 $30\%$ 的数据，有 $ n ≤ 200 , m ≤ 20$。对于 $60\%$ 的数据，有 $n ≤ 1000 , m ≤ 1000$。对于 $100\%$ 的数据，有 $1 ≤ n≤ 10^6，1 ≤ x_i ≤ m ≤ 2 × 10^3$。

Samples

Input #1

12 5
2 5 3 1 3 2 4 1 1 5 4 3

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[CSP-X2022 山东] 动物园",
    "description": {
      "content": "某动物园里有 $n$ 个场馆和 $m$ 种动物（$m ≤ n$）。 $n$ 个场馆的编号分别用 $1,2,3, . . , n$ 表示；$m$ 种动物的编号分别用 $1,2,3, . . , m$ 表示。每一个场馆中只饲养了一只动物，不同的场馆可能饲养着相同种类的动物。 这个动物园的门票比较特殊，游客在购买门票时必须说明要参观的场馆的起止编号 $a$ 和 $b$（起止编号会打印到游客购买的门票",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4098"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "某动物园里有 $n$ 个场馆和 $m$ 种动物（$m ≤ n$）。\n\n$n$ 个场馆的编号分别用 $1,2,3, . . , n$ 表示；$m$ 种动物的编号分别用 $1,2,3, . . , m$ 表示。每一个场馆中只饲养了一只动物，不同的场馆可能饲养着相同种类的动物。\n\n这个动物园的门票比较特殊，游客在购买门票时必须说明要参观的场馆的起止编号 $a$ 和 $b$（起止编号会打印到游客购买的门票...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments