狙击手

[编程题]狙击手

热度指数：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

算法知识视频讲解

Java

Sen🍓🍀

import java.util.*;

// 初始入度0的必活、自环必死 🔥
// 最大存活：初始入度0的开枪后, 目标死, 目标的目标入度-1, 类似拓扑排序, 其他环存活一半(向下取整5/2=1)
// 最小存活：初始入度0指向的环存活0个, 其他环存活1个

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] target = new int[n + 1]; // 瞄准目标
        int[] indeg = new int[n + 1];  // 入度
        for (int i = 1; i <= n; i++) {
            int t = in.nextInt();
            target[i] = t;
            indeg[t]++;
        }

        int max = getMax(target, indeg.clone(), n); // clone副本, 函数里要修改内容
        int min = getMin(target, indeg.clone(), n);
        System.out.printf("%d\n%d", min, max);
    }

    // 最多存活
    static int getMax(int[] target, int[] indeg, int n) {
        int res = 0;
        Deque<Integer> q = new ArrayDeque<>();
        boolean[] used = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            if (indeg[i] == 0 || target[i] == i) { // 初始入度0 || 自环
                used[i] = true;
                if (indeg[i] == 0) {
                    q.offer(i);
                    res++;
                }
            }
        }

        while (!q.isEmpty()) { // 初始入度0的开枪, 可能产生新的入度0
            int i = q.poll();
            if (!used[target[i]]) { // if 仅下个目标
                used[target[i]] = true;
                int t = target[target[i]];
                if (--indeg[t] == 0) {
                    used[t] = true;
                    q.offer(t);
                    res++;
                }
            }
        }

        for (int i = 1; i <= n; i++) { // 剩余的环：每个环最多活size/2个
            if (used[i]) continue;
            int t = i, size = 0;
            while (!used[t]) {
                size++;
                used[t] = true;
                t = target[t];
            }
            res += size / 2;
        }
        return res;
    }

    // 最少存活
    static int getMin(int[] target, int[] indeg, int n) {
        int res = 0;
        Deque<Integer> q = new ArrayDeque<>();
        boolean[] used = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            if (indeg[i] == 0 || target[i] == i) { // 初始入度0 || 自环
                used[i] = true;
                if (indeg[i] == 0) {
                    q.offer(i);
                    res++;
                }
            }
        }

        while (!q.isEmpty()) { // 初始入度0指向的环全灭
            int i = q.poll();
            while (!used[target[i]]) {  // while 处理环
                used[target[i]] = true;
                i = target[i];
            }
        }

        for (int i = 1; i <= n; i++) { // 剩余的环：每个环最多活1个
            if (used[i]) continue;
            int t = i;
            while (!used[t]) {
                used[t] = true;
                t = target[t];
            }
            res++;
        }
        return res;
    }
}

发表于 2025-10-24 18:48:18 回复(0)