解题思路

这是一道树形DFS问题,需要:

  1. 构建推荐关系树(使用邻接表)
  2. 计算每个客户的推荐链下线总数
  3. 筛选出满足条件(下线数不小于 )的客户

关键点:

  1. 使用 map 存储推荐关系
  2. 使用 DFS 递归统计下线数量
  3. 对结果进行排序输出

代码

#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(深度优先搜索)
  • 时间复杂度: - 其中 是客户数量, 是推荐关系数量
  • 空间复杂度: - 需要存储结果数组和递归栈