[NERC 2018] Lazyland

Luogu
IDLGP9802
Time2000ms
Memory512MB
DifficultyP3
贪心2018排序ICPCNERC/NEERC
一个城市里有 $n$ 个人,和 $k$ 种职业,其中,每个人都有一个现在正在从事的职业 $a_i$,但是很遗憾,由于某些职业的空缺,使得这个城市根本无法继续正常生存下去。 你作为一城之主,自然不希望看到自己的城市这样子下去,你决定说服其中的某些人,使得每种职业都有人在做,对于每个人 $i$,你需要耗费 $b_i$ 的时间去说服。 你需要求出你去说服的时间的最小值。 ## Input 第一行两个整数 $n$ 和 $k (1 \leq k \leq n \leq 10^5)$,分别表示 $n$ 个人和 $k$ 种职业。 第二行 $n$ 个整数 $a_i (1 \leq a_i \leq k)$,表示第 $i$ 个人正在从事的职业 。 第三行 $n$ 个整数 $b_i (1 \leq b_i \leq 10^9)$,表示第 $i$ 个人被说服去做别的职业的时间。 ## Output 输出去说服市民的最小时间。 [samples] ## Background 翻译自 [NERC 2018](https://neerc.ifmo.ru/archive/2018/neerc-2018-statement.pdf) L 题。 ## Note 对于所有的数据,保证 $1 \leq k \leq n \leq 10^5$,$1 \leq a_i \leq k$,$1 \leq b_i \leq 10^9$。 对于样例一,分别令 $1$,$6$,$8$ 号市民去从事 $2$,$4$,$6$ 号职业。
Samples
Input #1
8 7
1 1 3 1 5 3 7 1
5 7 4 8 1 3 5 2
Output #1
10
Input #2
3 3
3 1 2
5 3 4
Output #2
0
API Response (JSON)
{
  "problem": {
    "name": "[NERC 2018] Lazyland",
    "description": {
      "content": "一个城市里有 $n$ 个人,和 $k$ 种职业,其中,每个人都有一个现在正在从事的职业 $a_i$,但是很遗憾,由于某些职业的空缺,使得这个城市根本无法继续正常生存下去。 你作为一城之主,自然不希望看到自己的城市这样子下去,你决定说服其中的某些人,使得每种职业都有人在做,对于每个人 $i$,你需要耗费 $b_i$ 的时间去说服。 你需要求出你去说服的时间的最小值。",
      "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": "LGP9802"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一个城市里有 $n$ 个人,和 $k$ 种职业,其中,每个人都有一个现在正在从事的职业 $a_i$,但是很遗憾,由于某些职业的空缺,使得这个城市根本无法继续正常生存下去。\n\n你作为一城之主,自然不希望看到自己的城市这样子下去,你决定说服其中的某些人,使得每种职业都有人在做,对于每个人 $i$,你需要耗费 $b_i$ 的时间去说服。\n\n你需要求出你去说服的时间的最小值。\n\n## Input\n\n第一行...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments