贪心——烈焰风暴（用最少的线段去覆盖最多的点）

浅浅的花香味﹌ 2022-07-13 14:19 139阅读 0赞

**贪心——局部最优递推到整体最优**  
**本题——记录覆盖点->最少线段**

## 最少的线段去覆盖最多的点 ##

**题目**  
现在，一些小兵排列整齐以一条线的方式，通过传送门进攻你的大本营。

为了简化问题，我们假设烈焰风暴的作用范围是一个半径为 R 的圆（包括圆上的点），可以秒杀作用范围内的数量不限的小兵。所有小兵都在一条直线上，其位置以坐标的形式给出，并且给出烈焰风暴的作用半径以及释放一次技能所需要的魔法值 m，请你求出至少需要多少魔法才能杀死所有小兵。  
**Input**

输入数据有多组（**数据组数不超过 200**），到 EOF 结束。

对于每组数据：

第 1 行先给出小兵数量 n (1 <= n <= 1000)，半径 R (1 <= R <= 20) 和魔法值 m (1 <= m <= 100)。
    第 2 行输入 n 个小兵的坐标 x (0 <= x <= 10000)。

输入数据均为整数，一行内的整数两两之间用空格隔开。  
**Output**

在输出的最开始一行先输出 ”Good Luck” （**无论几组数据它只在开头输出一次**）。

对于每组数据，先输出 ”Case \#i: ” (**i 从 1 开始计数**)，表示当前是第几组数据，之后输出**至少需要的魔法**。

在所有数据都处理完后，输出一行 ”QAQ”。

上述输出均不包含引号。  
**Example Input**

5 2 4  
1 2 3 4 5  
5 2 4  
1 2 4 6 5

**Example Output**

Good Luck  
Case \#1: 4  
Case \#2: 8  
QAQ

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    int main()
    {
        int n, r, m, a[10004], i, j, t, k, sum, pos;
        printf("Good Luck\n");
        k = 1;
        while(scanf("%d %d %d", &n, &r, &m) != EOF)
        {
            sum = 1;
            for(i = 0; i < n; i++)
            {
                scanf("%d", &a[i]);
            }
            for(i = 0; i < n; i++)
            {
                for(j = 0; j < n-1-i; j++)
                {
                    if(a[j] > a[j+1])
                    {
                        t = a[j], a[j] = a[j+1], a[j+1] = t;
                    }
                }
            }
            pos = a[0];
            for(i = 1; i < n; i++)
            {
                if(a[i] - pos > 2*r)
                {
                    sum++;
                    pos = a[i];
                }
            }
            printf("Case #%d: %d\n", k++, sum*m);
        }
        printf("QAQ\n");
        return 0;
    }