动态规划1111111

Question

卡塔尔世界杯正在火热进行中，P大富哥李哥听闻有一种叫"肤白·态美·宇宙无敌·世界杯·预测鸡"的鸡品种（以下
简称为只因）有概率能准确预测世界杯赛果，一口气买来无数只只因，并把它们塞进了N个只因窝里，但只因窝实在太
多了，李哥需要安装摄像头来观测里面的只因的预测行为。
具体来说，李哥的只因窝可以看作分布在一条直线上的N个点，编号为1到N。由于每个只因窝的结构不同，在编号为i
的只因窝处安装摄像头，观测范围为a_i，其中a是长为N的整数列，表示若在此安装摄像头，可以观测到编号在
[ i - a_i , i + a_i ]（闭区间）内的所有只因窝。
李哥觉得摄像头成本高，决定抠门一下，请你来帮忙看看最少需要安装多少个摄像头，才能观测到全部N个只因窝。作
为回报，他会请你喝一杯芋泥波波牛乳茶。

关于输入

第一行：一个正整数，代表有N个只因窝。
第二行给出数列a：N个非负整数，第i个数代表a_i，也就是在第i个只因窝装摄像头能观测到的区间的半径。
数据保证 N ≦ 500000，0 ≦ a_i ≦ N

关于输出

一个整数，即最少需要装的摄像头数量。

例子输入

10
2 0 1 1 0 3 1 0 2 0

例子输出

3

提示信息

由于数据量较大，建议使用scanf进行读入，即
int n;
scanf("%d", &n);
请注意所使用算法的运行效率

Answer 1

让【道友老李】来帮你解答，本回答参考通义千问qwen-plus编写，并整理提供，如果还有疑问可以点击头像关注，评论或留言

要解决这个问题，我们可以使用贪心算法。具体思路是每次选择能够覆盖最远距离的摄像头，这样可以最大限度地减少摄像头的数量。

算法步骤：

1. 初始化：读取输入数据，包括只因窝的数量 ( N ) 和每个只因窝的观测范围 ( a_i )。
2. 排序：将只因窝按其左边界从小到大排序，如果左边界相同，则按右边界从大到小排序。
3. 贪心选择：从左到右遍历排序后的只因窝，每次选择能够覆盖最远距离的摄像头，并更新当前已覆盖的最大位置。
4. 统计结果：记录所需的摄像头数量。

具体实现：

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

typedef struct {
    int left;
    int right;
} Range;

// 比较函数，用于qsort排序
int compare(const void *a, const void *b) {
    Range *rangeA = (Range *)a;
    Range *rangeB = (Range *)b;
    if (rangeA->left == rangeB->left) {
        return rangeB->right - rangeA->right;
    }
    return rangeA->left - rangeB->left;
}

int minCameras(int N, int *a) {
    Range ranges[N];
    
    // 计算每个只因窝的观测范围
    for (int i = 0; i < N; i++) {
        ranges[i].left = i - a[i];
        ranges[i].right = i + a[i];
    }
    
    // 按左边界排序，如果左边界相同，则按右边界从大到小排序
    qsort(ranges, N, sizeof(Range), compare);
    
    int cameras = 0;
    int currentRight = -1;
    
    // 遍历排序后的范围
    for (int i = 0; i < N; i++) {
        if (ranges[i].left > currentRight) {
            // 当前范围无法被覆盖，需要一个新的摄像头
            cameras++;
            currentRight = ranges[i].right;
        }
    }
    
    return cameras;
}

int main() {
    int N;
    scanf("%d", &N);
    
    int a[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &a[i]);
    }
    
    int result = minCameras(N, a);
    printf("%d\n", result);
    
    return 0;
}

解释：

1. Range 结构体：用于存储每个只因窝的观测范围。
2. compare 函数：用于 qsort 排序，确保按左边界从小到大排序，如果左边界相同，则按右边界从大到小排序。
3. minCameras 函数：
   • 计算每个只因窝的观测范围。
   • 使用 qsort 对观测范围进行排序。
   • 遍历排序后的范围，使用贪心策略选择摄像头。
4. main 函数：
   • 读取输入数据。
   • 调用 minCameras 函数计算最小摄像头数量。
   • 输出结果。

这个算法的时间复杂度主要由排序决定，为 ( O(N \log N) )，适合处理题目给定的数据规模。