题目描述

在一个数轴上有若干个区间(区间端点均为整数),每个区间的长度均为1,现用整数集M表示区间,且M中的数仅表示各区间的右端点,假设M中有m个元素,现有n条线段(m > n),试设计一个算法求出用这些线段将所有区间覆盖后的最短距离之和d。例:M = {1, 3, 4, 8, 11, 14},n = 3

解题策略

首先要读懂题意,要用n条线段覆盖所有区间,求n条线段的最短距离和,自己当时看了半天,最后理解错了,每条线段可以任意长哦,而不是固定的

  1. 先假定一条线段覆盖所有区间,求出此时线段的最大长度
  2. 然后采用贪心策略,因为是n条线段,所以可以有n-1个间距
  3. 将题目中给定的区间进行排序,并且算出相邻的区间的间距(公式:后一个区间的右端点 - 前一个区间的左端点),将间距从小到大排序
  4. 用上面一条线段覆盖时的最大长度 依次 减去间距中的最大值,一共减去n-1个间距(因为要n-1条线段)
  5. 剩下的距离就是我们题目要求的最短距离之和d

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
int M[10000];
int dist[10000];

void swap(int arr[], int index1, int index2)
{
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}

int partition(int arr[], int low, int high)
{
int pivot = arr[low];

while(low < high){
while((low < high) && (pivot <= arr[high]))
high--;
swap(arr, low, high);
while((low < high) && (pivot >= arr[low]))
low++;
swap(arr, low, high);
}
return low;
}

//从小到大的快速排序
void quickSort(int arr[], int low, int high)
{
if (low < high) {
int part = partition(arr, low, high);
quickSort(arr, low, part-1);
quickSort(arr, part+1, high);
}
}

void main()
{
int m;
printf("请输入区间个数:");
scanf("%d", &m);

int n;
printf("请输入线段条数:");
scanf("%d", &n);

for(int i = 1; i <= m; i++)
{
printf("请输入区间%d的右端点:", i);
scanf("%d", &M[i]);
}
//对区间右端点进行排序,从小到大
quickSort(M, 1, m);

//计算间距
for(int i = 1; i <= m-1; i++)
//第i个区间到第i+1个区间的距离
dist[i] = M[i+1] - 1 - M[i];

quickSort(dist, 1, m-1);


int sum = M[m] - M[1] + 1; //用来计算覆盖后的最短距离和
for(int i = m; i > m-n+1; i--)
sum -= dist[i-1];

printf("最小长度和为:%d\n", sum);
}

参考

区间覆盖问题(思路)

区间覆盖问题(思路)

区间覆盖问题(思路 PPT 10页)

区间覆盖问题(代码)