题解 | 小红的矩阵染色[C语言]

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

int comfunc(const void* a, const void* b)
{
    return (*(int*)b - *(int*)a);  // 降序排列
}

int main() {
    int row, column, cost;
    scanf("%d %d %d", &row, &column, &cost);
    
    char map[1001][1001] = {0};
    int segments[1000010] = {0};  // 存储所有连续白色段的长度
    int index = 0;
    
    // 读取矩阵
    for (int i = 0; i < row; i++)
    {
        scanf("%s", map[i]);
    }
    
    // 遍历每一列，找出所有连续白色段
    for (int j = 0; j < column; j++)
    {
        int pos = 0;
        while(pos < row)
        {
            // 跳过黑色格子
            while(pos < row && map[pos][j] == '*') {
                pos++;
            }
            
            // 统计连续白色段长度
            int count = 0;
            while(pos < row && map[pos][j] == 'o') {
                count++;
                pos++;
            }
            
            // 记录2个及以上的白色段
            if (count > 1) {
                segments[index++] = count;
            }
        }
    }
    
    // 按长度降序排序（长的段优先，因为性价比更高）
    qsort(segments, index, sizeof(segments[0]), comfunc);
    
    int score = 0;
    int remaining = cost;
    
    // 贪心选择：优先选长的段
    for (int i = 0; i < index; i++)
    {
        if (remaining >= segments[i]) { // 可以完整染这个段      
            remaining -= segments[i];
            score += segments[i] - 1;  // 段内得分为长度-1
        } else {
            // 只能染部分，但要注意：染部分可能无法获得完整得分
            // 为了简化，我们假设剩余名额可以来自一个段的开头部分
            if (remaining > 1) {
                score += remaining - 1;
            }
            break;
        }
    }
    
    printf("%d", score);
    return 0;
}