Posts pythonTip 66 排队
Post
Cancel

pythonTip 66 排队

题目描述: 全班N(2<=N<=45)个人排成一排,但因为高矮不齐,需要进行调整。调整的方法是,不调换左右次序,只让若干人后退一步变为第2排,使第一排留下的人从左到右的身高按降序排列,即右边的人不比左边的人高。如果第2排的人还不按降序排列,则照此办理,即再让第2排的若干人后退一步变为第3排,这样继续下去,直到所有排的人都按身高从高到低排列。现在将每个人的身高保存在列表L中,给你L,请你找出一种使第一排留下的人数尽可能多的调整方法,输出第一排留下的人数P及最后调整完共有几排数K,P和K之间以一个空格隔开。

如,L=[130, 122, 112, 126, 126, 125, 120, 100], 则输出6 2。

示例: 输入: L = [130, 122, 112, 126, 126, 125, 120, 100] 输出: 6 2

分析: 这个题目我们分析一下,实际上是两个问题:

  1. 最长非递增子序列;
  2. 导弹拦截系统(acm); —- 这是一个 动态规划问题。

问题一: 最长非递增子序列

假设 nums[i] 是 以第 i 个元素结尾的最长子序列长度为 nums[i] 。

如何求 nums[i] 呢?

  1. 令 nums[i] = 1。 表示只有 它 自己一个元素。
  2. 依次和前 i - 1 个元素做比较。
  3. 如果 nums[i] > nums[j], 则表示 第 i 个 元素,不能接在 第 j 个元素的后面。
  4. 如果 nums[i] <= nums[j], 则表示 第 i 个元素可以接在第 j 元素的后面,nums[i] = max(nums[i], nums[j] + 1)
1
2
3
4
5
6
7
8
9
nums = [1 for _ in L]


for i in range(1, len(L)):
    for j in range(0, i):
        if L[i] <= L[j]:
            nums[i] = max(nums[i], nums[j]+1)

ans = max(nums)

问题二: 导弹拦截系统(acm)

导弹拦截系统:有不同高度的导弹飞过来,现在导弹拦截系统对这些导弹进行拦截,但是这个拦截系统有bug,每次拦截的高度不能高于上一次拦截的高度,问拦截所有导弹需要至少需要几套这样的系统?

算法:

  1. 首先将所有导弹标记为 未拦截
  2. 开始遍历所有导弹
    1. 导弹状态 已拦截 ,那就没事。
    2. 导弹状态 未拦截。则判断当前导弹的高度和当前拦截系统的高度。拦截以后都将把导弹标记为 已拦截
      1. 如果导弹高度 > 当前拦截系统高度,则需要一个新的拦截系统,并且新的拦截系统的最大高度就是当前导弹的高度。
      2. 如果 导弹高度 <= 当前拦截系统高度,则当前导弹拦截系统的高度变为当前导弹的高度。
1
2
3
4
5
6
7
8
9
10
nums = [0 for _ in L]
res = 0
for index, value in enumerate(L):
    if not nums[index]:
        res += 1
        for j in range(index+1, len(L)):
            if L[j] <= value:
                value = L[j]
                nums[j] = 1

再好好想想,其实这个导弹拦截系统问题,和我们的题目问题实际上是一样的,一排不行就下一排,一套系统不行就新一套系统。 并且都是从高到低。

虽然题目要求第一排站的人要足够多,但是不管怎样最终站多少排是固定的。

你品,你细品。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
nums = [1 for _ in L]


for i in range(1, len(L)):
    for j in range(0, i):
        if L[i] <= L[j]:
            nums[i] = max(nums[i], nums[j]+1)

ans = max(nums)

nums = [0 for _ in L]
res = 0
for index, value in enumerate(L):
    if not nums[index]:
        res += 1
        for j in range(index+1, len(L)):
            if L[j] <= value:
                value = L[j]
                nums[j] = 1

print(ans, res)
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 65 RSA密码方程

pythonTip 67 101位自复制数

Trending Tags