解题思路
这是一道关于生存博弈的图论问题。主要思路如下：
-
问题分析：
个狙击手，每人瞄准一个目标
- 需要找出最少和最多生存人数
- 可以将问题转化为有向图问题
- 每个狙击手是一个节点，瞄准关系构成边
-
优化思路：
- 最大生存数：优先处理入度为0的节点
- 最小生存数：处理环和链的特殊情况
- 使用father数组记录入度
- 使用visit数组标记访问状态
-
关键点：
- 处理无入度节点（必定生存）
- 处理自环节点（必定生存）
- 处理普通环（可以最大/最小化生存数）
代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
int target[MAXN]; // 目标数组
bool visit[MAXN]; // 访问标记
int father[MAXN]; // 入度数组
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, ans;
cin >> n;
// 读入数据并统计入度
for(int i = 1; i <= n; i++) {
cin >> target[i];
father[target[i]]++;
}
// 计算最大生存数
ans = 0;
for(int i = 1; i <= n; i++) {
if(father[i] == 0) { // 处理入度为0的节点
visit[i] = true;
ans++;
int next = target[i];
while(!visit[next]) {
visit[next] = true;
next = target[next];
}
}
}
// 处理剩余的环
for(int i = 1; i <= n; i++) {
if(visit[i] || i == target[i]) continue;
visit[i] = true;
ans++;
int next = target[i];
while(!visit[next]) {
visit[next] = true;
next = target[next];
}
}
cout << ans << endl;
// 计算最小生存数
memset(visit, false, sizeof(visit));
ans = 0;
queue<int> q;
// 将入度为0的节点入队
for(int i = 1; i <= n; i++) {
if(father[i] == 0) q.push(i);
}
// 处理入度为0的节点
while(!q.empty()) {
int curr = q.front();
q.pop();
visit[curr] = true;
ans++;
int next = target[curr];
if(!visit[next]) {
visit[next] = true;
next = target[next];
father[next]--;
if(father[next] == 0) {
q.push(next);
}
}
}
// 处理剩余的环
for(int i = 1; i <= n; i++) {
if(visit[i] || i == target[i]) continue;
visit[i] = true;
int len = 1;
int next = target[i];
while(!visit[next]) {
len++;
visit[next] = true;
next = target[next];
}
ans += (len >> 1); // 环中最少生存人数为长度的一半
}
cout << ans << endl;
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
static final int MAXN = 1000005;
static int[] target = new int[MAXN];
static boolean[] visit = new boolean[MAXN];
static int[] father = new int[MAXN];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
// 读入数据并统计入度
for(int i = 1; i <= n; i++) {
target[i] = Integer.parseInt(st.nextToken());
father[target[i]]++;
}
// 计算最大生存数
int ans = getMaxSurvivors(n);
System.out.println(ans);
// 计算最小生存数
Arrays.fill(visit, false);
ans = getMinSurvivors(n);
System.out.println(ans);
}
static int getMaxSurvivors(int n) {
int ans = 0;
// 处理入度为0的节点
for(int i = 1; i <= n; i++) {
if(father[i] == 0) {
visit[i] = true;
ans++;
int next = target[i];
while(!visit[next]) {
visit[next] = true;
next = target[next];
}
}
}
// 处理剩余的环
for(int i = 1; i <= n; i++) {
if(visit[i] || i == target[i]) continue;
visit[i] = true;
ans++;
int next = target[i];
while(!visit[next]) {
visit[next] = true;
next = target[next];
}
}
return ans;
}
static int getMinSurvivors(int n) {
int ans = 0;
Queue<Integer> q = new LinkedList<>();
// 将入度为0的节点入队
for(int i = 1; i <= n; i++) {
if(father[i] == 0) q.offer(i);
}
// 处理入度为0的节点
while(!q.isEmpty()) {
int curr = q.poll();
visit[curr] = true;
ans++;
int next = target[curr];
if(!visit[next]) {
visit[next] = true;
next = target[next];
father[next]--;
if(father[next] == 0) {
q.offer(next);
}
}
}
// 处理剩余的环
for(int i = 1; i <= n; i++) {
if(visit[i] || i == target[i]) continue;
visit[i] = true;
int len = 1;
int next = target[i];
while(!visit[next]) {
len++;
visit[next] = true;
next = target[next];
}
ans += (len >> 1);
}
return ans;
}
}
from collections import deque
def get_max_survivors(n, target, father, visit):
ans = 0
# 处理入度为0的节点
for i in range(1, n + 1):
if father[i] == 0:
visit[i] = True
ans += 1
next_node = target[i]
while not visit[next_node]:
visit[next_node] = True
next_node = target[next_node]
# 处理剩余的环
for i in range(1, n + 1):
if visit[i] or i == target[i]:
continue
visit[i] = True
ans += 1
next_node = target[i]
while not visit[next_node]:
visit[next_node] = True
next_node = target[next_node]
return ans
def get_min_survivors(n, target, father, visit):
ans = 0
q = deque()
# 将入度为0的节点入队
for i in range(1, n + 1):
if father[i] == 0:
q.append(i)
# 处理入度为0的节点
while q:
curr = q.popleft()
visit[curr] = True
ans += 1
next_node = target[curr]
if not visit[next_node]:
visit[next_node] = True
next_node = target[next_node]
father[next_node] -= 1
if father[next_node] == 0:
q.append(next_node)
# 处理剩余的环
for i in range(1, n + 1):
if visit[i] or i == target[i]:
continue
visit[i] = True
length = 1
next_node = target[i]
while not visit[next_node]:
length += 1
visit[next_node] = True
next_node = target[next_node]
ans += length >> 1
return ans
n = int(input())
target = [0] + list(map(int, input().split()))
father = [0] * (n + 1)
visit = [False] * (n + 1)
# 统计入度
for i in range(1, n + 1):
father[target[i]] += 1
# 计算最大和最小生存数
print(get_max_survivors(n, target, father, visit))
visit = [False] * (n + 1)
print(get_min_survivors(n, target, father, visit))
算法分析
图论分析：
-
入度为0的点：
- 必定能存活
- 可以影响其目标的生存
-
环的处理：
- 自环：必定存活
- 普通环：
- 最大生存：可以全部存活
- 最小生存：只能存活一半
复杂度分析：
- 时间复杂度：
- 每个节点最多访问一次
- 空间复杂度：
- 需要存储目标数组和访问标记
京公网安备 11010502036488号