首页 > 试题广场 >

狙击手

[编程题]狙击手
  • 热度指数：531 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
N个狙击手在进行生死搏斗，每位狙击手各瞄准了一个目标，一旦开枪就会将被瞄准的目标消灭，被消灭的狙击手无法再开枪。已知任意两个狙击手不会同时开枪，但不知道他们的开枪顺序，所以无法确定最后哪些狙击手会存活下来。
请你求出最少可能存活多少个狙击手，最多可能存活多少个狙击手。

输入描述:
第一行一个正整数N 接下来一行N个正整数，第i个数字Ti表示第i个狙击手瞄准了第Ti个狙击手，注意可能存在Ti=i


输出描述:
两行，第一行是最少存活的狙击手的数量，第二行是最多存活的狙击手的数量
示例1

输入

8
2 3 2 2 6 7 8 5

输出

3
5

说明

样例解释：
最少存活的情况：2开枪消灭3，1开枪消灭2，7开枪消灭8，6开枪消灭7，5开枪消灭6，最后1, 4, 5存活。
最多存活的情况：1开枪消灭2，5开枪消灭6，7开枪消灭8，最后1，3，4，5，7存活。

数据约定：
20%   N≤10
50%   N≤10000
100%  N≤1000000,1≤Ti≤N
算法知识视频讲解
开通博客
头像 bandiaoz
发表于 2024-12-20 14:47:53
解题思路 这是一道关于生存博弈的图论问题。主要思路如下： 问题分析： 个狙击手，每人瞄准一个目标 需要找出最少和最多生存人数 可以将问题转化为有向图问题 每个狙击手是一个节点，瞄准关系构成边 优化思路： 最大生存数：优先处理入度为0的节点 最小生存数：处理环和链的特殊情况 使用fat 展开全文
去ta的博客 赞 (0) 回复(1) 收起

问题信息

C++工程师 动态规划 商汤科技 运维工程师 算法工程师 数据挖掘工程师 测试工程师 图 2018 大数据开发工程师 排序 Java工程师
上传者：小小
难度：
3条回答 5580浏览

热门推荐

通过挑战的用户

查看代码

相关试题

狙击手

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号