logo AlgoBeat OnlineJudge
登录 注册

#216330. [蓝桥杯 2026 省 Java B 组] 擂台赛

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

小蓝想要组织一场擂台赛,比赛共有 位选手,编号为 。初始时,每位选手 都在属于自己的第 号擂台上。每位选手 都有且仅有一个想要前往挑战的目标擂台

比赛开始时,小蓝需要制定一个出战顺序。按照该顺序,对于每一位出战选手

  • 如果他的目标擂台 目前未被关闭,他将离开自己的 号擂台并前往 号擂台发起挑战,同时关闭自己原先所在的擂台
  • 如果他的目标擂台 已被关闭,则他无法发起挑战,只能留在原地。

小蓝希望设置一个出战顺序,使得最终被使用过(即作为挑战目标被成功前往)的擂台数量尽可能少。需要注意的是,留在原地的选手并不计入对擂台的使用。

请你帮小蓝计算,在最优的出战顺序下,最少有多少个擂台被使用过?

输入格式

输入共 2 行。

第一行为一个正整数 ,表示选手数量。

第二行为 个正整数 ,表示每位选手的目标擂台编号。

输出格式

输出一个整数,表示最少被使用过的擂台数量。

样例

样例输入 1

5
2 3 4 5 4

样例输出 1

2

数据范围与提示

【样例说明】

其中一种最优的出战顺序为:

  1. 选手 挑战 :目标擂台 未关闭,出战成功,关闭擂台 ,使用擂台
  2. 选手 挑战 :目标擂台 未关闭,出战成功,关闭擂台 ,使用擂台
  3. 选手 挑战 :目标擂台 已被选手 出战时关闭,选手 只能留在原地;
  4. 选手 挑战 :目标擂台 未关闭,出战成功,关闭擂台 ,使用擂台
  5. 选手 挑战 :目标擂台 已被选手 出战时关闭,选手 只能留在原地。

最终被使用过的擂台为 ,共 个。

【评测用例规模与约定】

对于 的数据,

对于 的数据,