解题思路
这是一道树形DFS问题,需要:
- 构建推荐关系树(使用邻接表)
- 计算每个客户的推荐链下线总数
- 筛选出满足条件(下线数不小于
)的客户
关键点:
- 使用
map
存储推荐关系 - 使用 DFS 递归统计下线数量
- 对结果进行排序输出
代码
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int countRecommendations(char person, map<char, vector<char>>& recommendations,
vector<char>& result, int target) {
// 如果该人没有推荐他人
if (recommendations.find(person) == recommendations.end()) {
if (0 >= target) result.push_back(person);
return 0;
}
// 计算推荐链人数
int total = 0;
for (char recommended : recommendations[person]) {
total += countRecommendations(recommended, recommendations, result, target) + 1;
}
// 如果达到目标数量,加入结果集
if (total >= target) result.push_back(person);
return total;
}
int main() {
int m, n;
cin >> m >> n;
// 构建推荐关系图
map<char, vector<char>> recommendations;
for (int i = 0; i < m; i++) {
char recommender, recommended1, recommended2;
cin >> recommender >> recommended1 >> recommended2;
if (recommended2 != '*') {
recommendations[recommender] = {recommended1, recommended2};
} else {
recommendations[recommender] = {recommended1};
}
}
// 计算结果
vector<char> result;
countRecommendations('A', recommendations, result, n);
sort(result.begin(), result.end());
// 输出结果
if (result.empty()) {
cout << "None" << endl;
} else {
for (int i = 0; i < result.size(); i++) {
cout << (i == 0 ? "" : " ") << result[i];
}
cout << endl;
}
return 0;
}
import java.util.*;
public class Main {
static int countRecommendations(char person, Map<Character, List<Character>> recommendations,
List<Character> result, int target) {
// 如果该人没有推荐他人
if (!recommendations.containsKey(person)) {
if (0 >= target) result.add(person);
return 0;
}
// 计算推荐链人数
int total = 0;
for (char recommended : recommendations.get(person)) {
total += countRecommendations(recommended, recommendations, result, target) + 1;
}
// 如果达到目标数量,加入结果集
if (total >= target) result.add(person);
return total;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
sc.nextLine();
// 构建推荐关系图
Map<Character, List<Character>> recommendations = new HashMap<>();
for (int i = 0; i < m; i++) {
String line = sc.nextLine();
char recommender = line.charAt(0);
char recommended1 = line.charAt(2);
char recommended2 = line.charAt(4);
List<Character> list = new ArrayList<>();
list.add(recommended1);
if (recommended2 != '*') list.add(recommended2);
recommendations.put(recommender, list);
}
// 计算结果
List<Character> result = new ArrayList<>();
countRecommendations('A', recommendations, result, n);
Collections.sort(result);
// 输出结果
if (result.isEmpty()) {
System.out.println("None");
} else {
for (int i = 0; i < result.size(); i++) {
System.out.print((i == 0 ? "" : " ") + result.get(i));
}
System.out.println();
}
}
}
from collections import defaultdict
from typing import List, Dict
def count_recommendations(person: str, recommendations: Dict[str, List[str]],
result: List[str], target: int) -> int:
# 如果该人没有推荐他人
if person not in recommendations:
if 0 >= target:
result.append(person)
return 0
# 计算推荐链人数
total = 0
for recommended in recommendations[person]:
total += count_recommendations(recommended, recommendations, result, target) + 1
# 如果达到目标数量,加入结果集
if total >= target:
result.append(person)
return total
def main():
m, n = map(int, input().split())
# 构建推荐关系图
recommendations = defaultdict(list)
for _ in range(m):
recommender, recommended1, recommended2 = input().split()
recommendations[recommender].append(recommended1)
if recommended2 != '*':
recommendations[recommender].append(recommended2)
# 计算结果
result = []
count_recommendations('A', recommendations, result, n)
result.sort()
# 输出结果
if not result:
print("None")
else:
print(" ".join(result))
if __name__ == "__main__":
main()
算法及复杂度
- 算法:DFS(深度优先搜索)
- 时间复杂度:
- 其中
是客户数量,
是推荐关系数量
- 空间复杂度:
- 需要存储结果数组和递归栈