[已解决]区间覆盖问题

a327904410

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

最佳答案

月排行榜 / 总排行榜

jhq999

2022-2-22 21:35:59

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

以题目为例：

根据你提供的题意

1. #include <stdlib.h>
   
2. int aggregate(int (*areg)[2],int count)
   
3. {
   
4.         int i=0,j=0,sum=count;
   
5.         for (int i = 0; i < count; i++)
   
6.         {
   
7.                 for (int j = 0; j < count; j++)
   
8.                 {
   
9.                         if (i!=j)
   
10.                         {
    
11.                                 if((areg[i][0]>=areg[j][0])&&(areg[i][1]<=areg[j][1]))sum--;//只要其中一个是另一个子集数目就减1，当然也可以像排序一样优化复杂度，我就提供个思路
    
12.                         }
    
13.                 }
    
14.         }
    
15.         return sum;
    
16. }
    
17. int main()
    
18. {
    
19.         int num=0,count=0;
    
20.         scanf("%d",&num);
    
21. 
    
22.         int i=0,j=0,*result=(int*)malloc(4*num) ;
    
23.         for(i=0;i<num;i++)
    
24.         {
    
25.                 scanf("%d",&count);
    
26.                 int (*data)[2]=(int(*)[2])malloc(4*count*2);
    
27.                 for(j=0;j<count;j++)
    
28.                 {
    
29.                         scanf("%d%d",&data[j][0],&data[j][1]);
    
30.                 }
    
31.                 result[i]=aggregate(data,count);
    
32.                 free(data);
    
33.         }
    
34. 
    
35.         for(i=0;i<num;i++)printf("%d\n",result[i]);
    
36.         free(result);
    
37.         return 0;
    
38. }

复制代码

1. 2
   
2. 3
   
3. 1 1
   
4. 2 2
   
5. 3 3
   
6. 3
   
7. 1 1
   
8. 1 3
   
9. 3 3
   
10. 3
    
11. 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
我只读懂题目，但没有思路。

以题目为例：

根据你提供的题意

1. #include <stdlib.h>
   
2. int aggregate(int (*areg)[2],int count)
   
3. {
   
4.         int i=0,j=0,sum=count;
   
5.         for (int i = 0; i < count; i++)
   
6.         {
   
7.                 for (int j = 0; j < count; j++)
   
8.                 {
   
9.                         if (i!=j)
   
10.                         {
    
11.                                 if((areg[i][0]>=areg[j][0])&&(areg[i][1]<=areg[j][1]))sum--;//只要其中一个是另一个子集数目就减1，当然也可以像排序一样优化复杂度，我就提供个思路
    
12.                         }
    
13.                 }
    
14.         }
    
15.         return sum;
    
16. }
    
17. int main()
    
18. {
    
19.         int num=0,count=0;
    
20.         scanf("%d",&num);
    
21. 
    
22.         int i=0,j=0,*result=(int*)malloc(4*num) ;
    
23.         for(i=0;i<num;i++)
    
24.         {
    
25.                 scanf("%d",&count);
    
26.                 int (*data)[2]=(int(*)[2])malloc(4*count*2);
    
27.                 for(j=0;j<count;j++)
    
28.                 {
    
29.                         scanf("%d%d",&data[j][0],&data[j][1]);
    
30.                 }
    
31.                 result[i]=aggregate(data,count);
    
32.                 free(data);
    
33.         }
    
34. 
    
35.         for(i=0;i<num;i++)printf("%d\n",result[i]);
    
36.         free(result);
    
37.         return 0;
    
38. }

复制代码

1. 2
   
2. 3
   
3. 1 1
   
4. 2 2
   
5. 3 3
   
6. 3
   
7. 1 1
   
8. 1 3
   
9. 3 3
   
10. 3
    
11. 1

复制代码

傻眼貓咪

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

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

a327904410

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

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

傻眼貓咪

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

帮你简化 4楼 大佬的代码吧：希望对你有帮助

1. #include <stdio.h>
   
2. 
   
3. typedef struct{
   
4.     int x, y;
   
5. }Pair;
   
6. 
   
7. int overlapping(Pair *arr, size_t N){
   
8.     int sum = (int)N;
   
9.     for(int i = 0; i < N; i++)
   
10.     for(int j = 0; j < N; j++)
    
11.     if(i != j)
    
12.     if((arr[i].x >= arr[j].x) && (arr[i].y <= arr[j].y)) sum--;
    
13.     return sum;
    
14. }
    
15. 
    
16. int main()
    
17. {
    
18.     unsigned T, N;
    
19.     scanf("%u", &T);
    
20.     int results[T];
    
21.     for(int t = 0; t < T; t++){
    
22.         scanf("%u", &N);
    
23.         Pair data[N];
    
24.         for(int n = 0; n < N; n++) scanf("%d%d", &data[n].x, &data[n].y);
    
25.         results[t] = overlapping(data, N);
    
26.     }
    
27.     for(size_t i = 0; i < T; i++) printf("%d\n", results[i]);
    
28.     return 0;
    
29. }

复制代码

a327904410

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

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

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

复制代码

a327904410

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

3Q

傻眼貓咪

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

不客气