a327904410 发表于 2022-2-22 15:26:46

区间覆盖问题



没啥思路，题目也是半懂，求大佬指点{:10_245:}

傻眼貓咪 发表于 2022-2-22 18:23:55

我只读懂题目，但没有思路。

以题目为例：
输入若干区间，这里我把它们命名为子区间。
从子区间中选取并以最少子区间（当然可以重叠），满足 所有数字区间，比如题目：

样例 1：
3
1 1
2 2
3 3

表示 1 至 N = 1, 2, 3（子区间必须覆盖这三个数字）
目前有 3 个子区间，分别是 （只有覆盖数字 1），（只有覆盖数字 2），（只有覆盖数字 3）
所以 3 个字区间都要，才能确保全部数字被覆盖。
答案：3

// -------------------------------------------------------------------------------------------------------

样例 2：
3
1 1
1 3
3 3

表示 1 至 N = 1, 2, 3（子区间必须覆盖这三个数字）
目前有 3 个子区间，分别是 （只有覆盖数字 1），（此区间覆盖 1, 2, 3），（只有覆盖数字 3）
以最少子区间能覆盖所有数字就只需一个便可（就是 ）
答案：1

a327904410 发表于 2022-2-22 20:09:32

傻眼貓咪 发表于 2022-2-22 18:23
我只读懂题目，但没有思路。

以题目为例：


搜嘎，还是要感谢大佬的分析

jhq999 发表于 2022-2-22 21:35:59

本帖最后由 jhq999 于 2022-2-22 21:40 编辑

傻眼貓咪 发表于 2022-2-22 18:23
我只读懂题目，但没有思路。

以题目为例：


根据你提供的题意
#include <stdlib.h>
int aggregate(int (*areg),int count)
{
        int i=0,j=0,sum=count;
        for (int i = 0; i < count; i++)
        {
                for (int j = 0; j < count; j++)
                {
                        if (i!=j)
                        {
                                if((areg>=areg)&&(areg<=areg))sum--;//只要其中一个是另一个子集数目就减1，当然也可以像排序一样优化复杂度，我就提供个思路
                        }
                }
        }
        return sum;
}
int main()
{
        int num=0,count=0;
        scanf("%d",&num);

        int i=0,j=0,*result=(int*)malloc(4*num) ;
        for(i=0;i<num;i++)
        {
                scanf("%d",&count);
                int (*data)=(int(*))malloc(4*count*2);
                for(j=0;j<count;j++)
                {
                        scanf("%d%d",&data,&data);
                }
                result=aggregate(data,count);
                free(data);
        }

        for(i=0;i<num;i++)printf("%d\n",result);
        free(result);
        return 0;
}
2
3
1 1
2 2
3 3
3
1 1
1 3
3 3
3
1

傻眼貓咪 发表于 2022-2-22 21:50:05

jhq999 发表于 2022-2-22 21:35
根据你提供的题意

好厉害啊，我完全没有想到这点{:10_282:}{:10_257:}

a327904410 发表于 2022-2-22 22:08:45

jhq999 发表于 2022-2-22 21:35
根据你提供的题意

这个做法超出我认识了，不过还是感谢大佬解答。会好好看的{:10_256:}

傻眼貓咪 发表于 2022-2-22 22:22:28

a327904410 发表于 2022-2-22 22:08
这个做法超出我认识了，不过还是感谢大佬解答。会好好看的

帮你简化 4楼 大佬的代码吧：希望对你有帮助#include <stdio.h>

typedef struct{
    int x, y;
}Pair;

int overlapping(Pair *arr, size_t N){
    int sum = (int)N;
    for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
    if(i != j)
    if((arr.x >= arr.x) && (arr.y <= arr.y)) sum--;
    return sum;
}

int main()
{
    unsigned T, N;
    scanf("%u", &T);
    int results;
    for(int t = 0; t < T; t++){
      scanf("%u", &N);
      Pair data;
      for(int n = 0; n < N; n++) scanf("%d%d", &data.x, &data.y);
      results = overlapping(data, N);
    }
    for(size_t i = 0; i < T; i++) printf("%d\n", results);
    return 0;
}

a327904410 发表于 2022-2-22 22:24:27

jhq999 发表于 2022-2-22 21:35
根据你提供的题意

大佬，问下这段代码是什么意思？后面怎么变成了二维数组
int(*data) = (int(*))malloc(4 * count * 2);

a327904410 发表于 2022-2-24 22:55:14

傻眼貓咪 发表于 2022-2-22 22:22
帮你简化 4楼 大佬的代码吧：希望对你有帮助

3Q{:10_256:}

傻眼貓咪 发表于 2022-2-24 22:59:30

a327904410 发表于 2022-2-24 22:55
3Q

不客气{:10_254:}
页: [1]
查看完整版本: 区间覆盖问题