0%

机试——贪心算法

发表于 更新于 阅读次数： Valine：
本文字数： 285 阅读时长 ≈ 1 分钟

挑选代表

我们有很多区域，每个区域都是从a到b的闭区间，现在我们要从每个区间中挑选至少2个数，那么最少挑选多少个？

输入描述:
1
2
第一行是N（N<10000）,表示有N个区间，之间可以重复
然后每一行是ai,bi，持续N行，表示现在区间。均小于100000
输出描述:
1
输出一个数，代表最少选取数量。
输入例子1:
1
2
3
4
5
4
4 7
2 4
0 2
3 6
输出例子1:
1
4

思路分析：

​ 本题是一个贪心问题，即挑选最少的点，也就是在每一步种都选择可能和下一步公用的点。可以先把区间按照结尾去接进行排序，然后从第一个区间开始记录最后两个元素的值，

​ 如果下个区间中包含了这两个元素，那么挑选点数+0，x、y不变，

​ 如果下个区间中只包含了一个元素，那么挑选点数+1,y继承x的值，x变为当前区间的最后一个元素

​ 如果下个区间中不包含任何x、y一个元素，那么挑选点数+2，x、y更新为区间最大、次大值

1
这里之所以按照末尾元素进行排序，主要是因为后续要判断结尾两个元素和下一个区间是否具有关系
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
n = int(input())

nums = []
for _ in range(n):
    tmp = list(map(int,input().split()))
    nums.append(tmp)

nums = sorted(nums,key=lambda x:x[1])

ans = 2
x= nums[0][-1]   #最大的元素
y = nums[0][-1]-1    #次大的元素

for l in nums[1:]:
    if l[0]<=x<=l[-1] and  l[0]<=y<=l[-1]:
        ans += 0
    elif l[0]<=x<=l[-1] or l[0]<=y<=l[-1]:
        y = x
        x = l[-1]
        ans+=1
    else:
        ans+=2
        x = l[-1]
        y = l[-1] - 1

print(ans)