题意分析

本题是一个关于广告牌放置的优化问题，目标是在满足每个慢跑者至少看到K次广告的前提下，最小化放置的广告牌数量。题目中需要考虑两种情况：

1. 对于路径长度大于等于K的慢跑者，必须保证其路径上至少有K个广告牌
2. 对于路径长度小于K的慢跑者，必须保证其路径上的每个广告牌都被放置广告

解题思路

这是一个典型的差分约束系统问题，可以通过最大流或最短路算法来解决。基本思路是将问题转化为网络流问题，通过构建约束图并求解最大流来得到最小覆盖。

关键步骤：

1. 问题转化：将每个广告牌位置视为一个节点，每个慢跑者的路径视为一个约束条件
2. 差分约束：对于每个路径，建立相应的约束方程
3. 网络流建模：将约束条件转化为图的边，通过最大流算法求解
4. SPFA算法：使用SPFA算法（Shortest Path Faster Algorithm）求解差分约束系统

代码解释

原代码使用了SPFA算法来求解差分约束系统，主要分为以下几个部分：

1. 输入处理：读取K和N，处理每个慢跑者的路径，确保路径起点小于终点
2. 图的构建：根据路径长度和K的关系，构建不同的边权
3. 约束转换：将每个路径转换为差分约束条件，并添加相应的边
4. 最长路求解：使用SPFA算法求解最长路径，计算最小覆盖

关键代码部分：

// 添加边函数，构建约束图
void addedge(int x, int y, int w)
{
    ++m;
    e[m].x = x;
    e[m].y = y;
    e[m].w = w;
    e[m].next = head[x];
    head[x] = m;
}

// SPFA算法求解最长路
void spfa()
{
    int i, j, x, y, tail = 0, front = 0;
    for(i = minnum; i <= maxnum; ++i){
        if(i != 0){
            queue[++tail] = i;
            addedge(i, i + 1, 0);  // 普通边
            addedge(i + 1, i, -1); // 容量限制边
        }
        dis[i] = -maxint;
        vis[i] = 0;
    }
    dis[minnum] = 0;
    vis[minnum] = 1;
    
    // SPFA核心部分
    while(front < tail){
        x = queue[++front];
        vis[x] = 0;
        for(i = head[x]; i != -1; i = e[i].next){
            y = e[i].y;
            if(dis[x] + e[i].w > dis[y]){
                dis[y] = e[i].w + dis[x];
                if(!vis[y]){
                    vis[y] = 1;
                    queue[++tail] = y;
                }
            }
        }
    }
}

// 输出结果
void print()
{
    int i;
    printf("%d\n", dis[maxnum]);
    for(i = minnum; i <= maxnum; ++i)
        if(dis[i] - dis[i - 1] == 1 )
            printf("%d\n", i - num);  // 转换回原始坐标
}

算法复杂度

• 时间复杂度：O(N*M)，其中N是节点数，M是边数
• 空间复杂度：O(N+M)，主要用于存储图的邻接表

这个算法通过将问题转化为差分约束系统，并使用SPFA算法求解最长路径，有效地找到了满足所有约束条件的最小广告牌覆盖。