Hipster Jazz 题解

问题分析

我们需要为$N$个学生分配两种乐器（钢琴P或萨克斯S），使得对于每个学生，至少有一半的朋友选择了与自己不同的乐器。

这是一个图论约束满足问题：

• 学生作为图的节点
• 朋友关系作为边
• 每个节点的邻居中，不同乐器的数量要 ≥ 总度数的一半

核心思路：贪心调整算法

由于数据规模较小（$N \leq 200$），我们可以使用简单的贪心调整策略：

1. 随机初始化所有学生的乐器选择
2. 重复检查每个学生是否满足条件
3. 对于不满足条件的学生，翻转其乐器选择
4. 直到所有学生都满足条件为止

算法正确性

题目保证解存在，且由于每次调整都会改善不满足条件的情况，算法最终会收敛。

数据结构设计

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAXN 205

bool graph[MAXN][MAXN];  // 邻接矩阵存储朋友关系
int degree[MAXN];        // 每个学生的朋友数
char instrument[MAXN];   // 每个学生的乐器选择

完整代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

#define MAXN 205

bool graph[MAXN][MAXN];  // 邻接矩阵存储朋友关系
int degree[MAXN];        // 每个学生的朋友数
char instrument[MAXN];   // 每个学生的乐器选择

// 检查学生i是否满足条件
bool check_student(int i, int n) {
    if (degree[i] == 0) return true;  // 没有朋友，自动满足
    
    int diff_count = 0;
    for (int j = 1; j <= n; j++) {
        if (graph[i][j] && instrument[i] != instrument[j]) {
            diff_count++;
        }
    }
    
    // 检查是否至少有一半朋友选择不同乐器
    return diff_count * 2 >= degree[i];
}

// 贪心调整算法
void solve(int n) {
    // 随机初始化乐器选择
    for (int i = 1; i <= n; i++) {
        instrument[i] = (rand() % 2 == 0) ? 'P' : 'S';
    }
    
    bool changed;
    int max_iterations = 1000;  // 防止无限循环的安全措施
    
    do {
        changed = false;
        
        for (int i = 1; i <= n; i++) {
            if (!check_student(i, n)) {
                // 翻转当前学生的乐器选择
                instrument[i] = (instrument[i] == 'P') ? 'S' : 'P';
                changed = true;
            }
        }
        
        max_iterations--;
    } while (changed && max_iterations > 0);
}

int main() {
    srand(time(NULL));  // 初始化随机种子
    
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 初始化
    memset(graph, false, sizeof(graph));
    memset(degree, 0, sizeof(degree));
    
    // 读取朋友关系
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a][b] = true;
        graph[b][a] = true;
        degree[a]++;
        degree[b]++;
    }
    
    // 解决问题
    solve(n);
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        printf("%c", instrument[i]);
    }
    printf("\n");
    
    return 0;
}

优化版本：更稳定的算法

上面的随机初始化可能导致不同运行结果不同，下面是更稳定的版本：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAXN 205

bool graph[MAXN][MAXN];
int degree[MAXN];
char instrument[MAXN];
bool visited[MAXN];

// 检查学生i是否满足条件
bool check_student(int i, int n) {
    if (degree[i] == 0) return true;
    
    int diff_count = 0;
    for (int j = 1; j <= n; j++) {
        if (graph[i][j] && instrument[i] != instrument[j]) {
            diff_count++;
        }
    }
    
    return diff_count * 2 >= degree[i];
}

// 使用BFS思想进行初始化，提高稳定性
void initialize_instruments(int n) {
    memset(visited, false, sizeof(visited));
    
    for (int start = 1; start <= n; start++) {
        if (!visited[start]) {
            // BFS遍历连通分量
            int queue[MAXN];
            int front = 0, rear = 0;
            
            queue[rear++] = start;
            visited[start] = true;
            instrument[start] = 'P';  // 起始节点选择P
            
            while (front < rear) {
                int current = queue[front++];
                
                for (int neighbor = 1; neighbor <= n; neighbor++) {
                    if (graph[current][neighbor] && !visited[neighbor]) {
                        visited[neighbor] = true;
                        // 交替分配乐器
                        instrument[neighbor] = (instrument[current] == 'P') ? 'S' : 'P';
                        queue[rear++] = neighbor;
                    }
                }
            }
        }
    }
}

void solve_optimized(int n) {
    initialize_instruments(n);
    
    bool changed;
    int max_iterations = 1000;
    
    do {
        changed = false;
        
        for (int i = 1; i <= n; i++) {
            if (!check_student(i, n)) {
                instrument[i] = (instrument[i] == 'P') ? 'S' : 'P';
                changed = true;
                break;  // 修改后重新检查，提高效率
            }
        }
        
        max_iterations--;
    } while (changed && max_iterations > 0);
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    memset(graph, false, sizeof(graph));
    memset(degree, 0, sizeof(degree));
    
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a][b] = graph[b][a] = true;
        degree[a]++;
        degree[b]++;
    }
    
    solve_optimized(n);
    
    for (int i = 1; i <= n; i++) {
        printf("%c", instrument[i]);
    }
    printf("\n");
    
    return 0;
}

算法核心步骤详解

1. 初始化阶段

void initialize_instruments(int n) {
    // 使用BFS遍历图的连通分量
    // 为相邻节点交替分配不同乐器
    // 这样初始状态就接近满足条件
}

2. 条件检查函数

bool check_student(int i, int n) {
    int diff_count = 0;
    // 统计选择不同乐器的朋友数量
    for (每个朋友j) {
        if (instrument[i] != instrument[j]) diff_count++;
    }
    // 检查: diff_count >= degree[i] / 2
    return diff_count * 2 >= degree[i];
}

3. 调整循环

do {
    changed = false;
    for (每个学生i) {
        if (!check_student(i, n)) {
            // 翻转乐器选择
            instrument[i] = 另一种乐器;
            changed = true;
            break; // 修改后重新检查
        }
    }
} while (changed);

复杂度分析

• 时间复杂度: $O(k \cdot n^2)$，其中$k$是调整次数
• 空间复杂度: $O(n^2)$ 存储邻接矩阵
• 由于$n \leq 200$，完全在可接受范围内

样例验证

样例1

输入: 3 3
关系: 1-2, 1-3, 2-3
可能的输出: PSP
验证:
- 学生1(P): 朋友2(S),3(P) → 1/2不同 ✓
- 学生2(S): 朋友1(P),3(P) → 2/2不同 ✓  
- 学生3(P): 朋友1(P),2(S) → 1/2不同 ✓

样例2

输入: 5 6
关系: 1-2,1-3,1-5,2-4,3-5,4-5
输出: SPPSP

算法特点

1. 简单有效: 基于贪心调整，容易理解和实现
2. 保证收敛: 题目保证解存在，算法最终会找到解
3. 稳定性: 使用BFS初始化提高结果稳定性
4. 安全性: 设置最大迭代次数防止无限循环

这个C语言实现简洁高效地解决了问题，适用于题目给定的数据规模。