[已解决]区间覆盖问题

a327904410

没啥思路，题目也是半懂，求大佬指点

最佳答案

月排行榜 / 总排行榜

jhq999

2022-2-22 21:35:59

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

以题目为例：

根据你提供的题意

#include <stdlib.h>
int aggregate(int (*areg)[2],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[i][0]>=areg[j][0])&&(areg[i][1]<=areg[j][1]))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)[2]=(int(*)[2])malloc(4*count*2);
                for(j=0;j<count;j++)
                {
                        scanf("%d%d",&data[j][0],&data[j][1]);
                }
                result[i]=aggregate(data,count);
                free(data);
        }

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

2
3
1 1
2 2
3 3
3
1 1
1 3
3 3
3
1

跳转到最佳答案楼层

傻眼貓咪

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

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

样例 1：
3
1 1
2 2
3 3

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

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

样例 2：
3
1 1
1 3
3 3

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

a327904410

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

以题目为例：

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

jhq999

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

以题目为例：

根据你提供的题意

#include <stdlib.h>
int aggregate(int (*areg)[2],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[i][0]>=areg[j][0])&&(areg[i][1]<=areg[j][1]))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)[2]=(int(*)[2])malloc(4*count*2);
                for(j=0;j<count;j++)
                {
                        scanf("%d%d",&data[j][0],&data[j][1]);
                }
                result[i]=aggregate(data,count);
                free(data);
        }

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

2
3
1 1
2 2
3 3
3
1 1
1 3
3 3
3
1

傻眼貓咪

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

好厉害啊，我完全没有想到这点

a327904410

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

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

傻眼貓咪

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[i].x >= arr[j].x) && (arr[i].y <= arr[j].y)) sum--;
    return sum;
}

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

a327904410

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

大佬，问下这段代码是什么意思？后面怎么变成了二维数组

int(*data)[2] = (int(*)[2])malloc(4 * count * 2);

a327904410

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

3Q

傻眼貓咪

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

不客气