PTA:Python解答1045 快速排序/1046 划拳

1045 快速排序 (25分)

著名的快速排序算法里有一个经典的划分过程:我们通常采用某种方法取一个元素作为主元,通过交换,把比主元小的元素放到它的左边,比主元大的元素放到它的右边。 给定划分后的 N 个互不相同的正整数的排列,请问有多少个元素可能是划分前选取的主元?
例如给定 $N = 5$, 排列是1、3、2、4、5。则:

  • 1 的左边没有元素,右边的元素都比它大,所以它可能是主元;
  • 尽管 3 的左边元素都比它小,但其右边的 2 比它小,所以它不能是主元;
  • 尽管 2 的右边元素都比它大,但其左边的 3 比它大,所以它不能是主元;
  • 类似原因,4 和 5 都可能是主元。

因此,有 3 个元素可能是主元。

输入格式:

输入在第 1 行中给出一个正整数 N(≤10^5); 第 2 行是空格分隔的 N 个不同的正整数,每个数不超过 10^​9。

输出格式:

在第 1 行中输出有可能是主元的元素个数;在第 2 行中按递增顺序输出这些元素,其间以 1 个空格分隔,行首尾不得有多余空格。

输入样例:

5
1 3 2 4 5

输出样例:

3
1 4 5

解题思路:

首先依次找最大元素,最大元素可以保证其前面的数都小于它,当后移的查找过程中有小于的,再在前面找到的最大元素中进行排除。

完整代码:

n = int(input())
a = [int(i) for i in input().split()]
result = []
max = 0
for i in range(n):
    if a[i]>max:
        result.append(a[i])
        max = a[i]
    else:
        for j in range(len(result)-1,-1,-1):
            if result[j]>=a[i]:
                del result[j]
            else:
                break
result.sort()
print(len(result))
if len(result)!=0:
    result = list(map(str,result))
    print(" ".join(result))
else:
    print("")
1046 划拳 (15分)

划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为:每人口中喊出一个数字,同时用手比划出一个数字。如果谁比划出的数字正好等于两人喊出的数字之和,谁就赢了,输家罚一杯酒。两人同赢或两人同输则继续下一轮,直到唯一的赢家出现。
下面给出甲、乙两人的划拳记录,请你统计他们最后分别喝了多少杯酒。

输入格式:

输入第一行先给出一个正整数 N(≤100),随后 N 行,每行给出一轮划拳的记录,格式为:

甲喊 甲划 乙喊 乙划

其中是喊出的数字,是划出的数字,均为不超过 100 的正整数(两只手一起划)。

输出格式:

在一行中先后输出甲、乙两人喝酒的杯数,其间以一个空格分隔。

输入样例:

5
8 10 9 12
5 10 5 10
3 8 5 12
12 18 1 13
4 16 12 15

输出样例:

1 2

解题思路:

这道题需要注意的是,输出的是喝酒的杯数,不是赢的次数。

完整代码:

n = eval(input())
ls = []
for i in range(n):
    m = list(map(eval,input().split()))
    ls.append(m)
ac = 0
bc = 0
for i in ls:
    if i[1] != i[0]+i[2] and i[3] != i[0]+i[2]:
        continue
    else:
        if i[1] != i[0]+i[2]:
            ac += 1
        if i[3] != i[0]+i[2]:
            bc += 1
print(ac,bc)
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注