当前位置:   article > 正文

Python解题 - CSDN周赛第26期 - 任务分配_python 分配问题

python 分配问题

本期除了第三题有点小坑,其他题都是几行代码的事。


第一题:等差数列

一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...)的数列。在这个问题中a是一个非负的整数,b是正整数。 现给出三个整数,分别表示等差数列的第一项a、最后一项、公差b,求该数列的和。

输入描述:输入三个整数,之间用空格隔开。第1个数作为首项(0≤a≤1e10),第2个数作为末项(0<c≤1e10),第3个数作为公差(0<b≤1000).

输出描述:输出占一行,包含一个整数,为该等差数列的和。如果所给三个整数,不能构成等差数列,则返回-1。
示例:

示例一
输入2 11 3
输出26

分析

本题关键是怎样理解“不能构成等差数列”的情况。根据题意,首项 a,末项 n,和公差 b 都已经给出,那么只要检查首项和末项是否同时存在数列中即可。

我们可以固定 a 为首项,以末项 n 为终点,设置步长为 b,生成一个 range 对象,它自然是一个等差数列。然后只要检查生成的等差数列的末项是不是 n(检查 n 是否在此 range 中即可)。

参考代码

  1. a, n, b = map(int, input().strip().split())
  2. nums = range(a, n+1, b)
  3. if n in nums:
  4. print(sum(nums))
  5. else:
  6. print(-1)

第二题:阿波罗的魔力宝石

在希腊神话中,有一个神祗阿波罗。阿波罗拥有一枚能够使人变得更加聪明的神奇宝石。但是,这枚宝石的魔力被封印在了一个混乱的顺序中,你需要通过排序的方法才能拥有这枚宝石的魔力。 给定一个长度为 N 的整数数组 A,请你将数组 A中的元素进行冒泡排序。
输入描述: 第一行包含整数 N(0<N<100000)。 第二行包含 N 个整数(0≤X<100000),表示数组 A。
输出描述: 输出N行,每行包含一个整数,表示排序后的数组 A。
示例:

示例一
输入5
2 5 3 1 4
输出

1

2

3

4

5

分析

题目的本质是排序,但只是从字面去要求冒泡排序是没用的,因为只要答案正确,就能pass,凡是 Online Judge 的比赛都不会检查代码实现的过程。而且冒泡排序的复杂度是 O(n^{2}),python自带的sort方法排序,快排、归并等,都是 O(nlogn),如果以本题的数据范围 0< N < 100000,乖乖地使用冒泡排序,反而有可能不通过(Python使用传统排序方法实现排序的效率要比C++差许多)。

参考代码

  1. n = int(input())
  2. nums = map(int, input().strip().split())
  3. print(*sorted(nums), sep="\n")

如果感兴趣的话,你也可以手写冒泡试试,网上模板很多,这里就不啰嗦了。 


第三题:任务分配问题

小明手头上有n个问题,每个问题都有一个数值,表示这个问题的难度;正好小明团队有n个人,每个人都有一个数值,表示这个人的能力。现在小明要把这n个问题分配给每个人,要求能力更高的人分配到更高难度的问题。

输入描述:第1行包含一个数字 n (n <= 100000),表示小明手头上有n个问题,团队有n个人 第2行到第n+1行,每一行包含1个数字,表示n个问题的难度(正整数,小于10^9)。第n+2到2n+1行,每一行包含一个数字,表示团队n个人的能力值(正整数,小于10^9)。

输出描述:输出n行,按输入的顺序,输出每个人分配到的问题的难度,如果有两个人能力值相同,那么输入的顺序靠前,分配到更高难度的问题。

示例:

示例一
输入3
1
2
3
3
2
1
输出

3

2

1

分析

思路很明显,先排序,把难度最大的任务按次序分给能力最大的人,然后最后按照每个人出现的顺序输出任务就好。但是这里存在一个小坑,就是“如果有两个人能力值相同,那么输入的顺序靠前,分配到更高难度的问题。”如果直接对人的能力采用降序排序,能力相同的人的位置会发生改变。比如,如果有4个人,输出的顺序以能力代表分别是,1,2,2,3,如果使用sort加reverse关键字按能力从大到小排序,中间两个2的位置会发生翻转,于是对应难度值降序排列的任务时,能力相同但是后输入的人对应的难度更高,这样便得不到正确答案。

对于此类问题(需要降序排列,但要保持正序排列的相对位置),有个常用的小技巧,就是把数组每个数字都转成负数,然后再来一遍升序排列,相对位置即可保持不变。而此题的数组转换成负数后,对应的其实就是能力最大的人,不需要再把负数转变回去,只要将难度降序排列的任务对应上就好。

在代码实现上,我使用了 zip 函数将输入的顺序变成一个二元组,最后再将结果的对应位置放入任务。

参考代码

  1. n = int(input().strip())
  2. task = [int(input().strip()) for _ in range(n)]
  3. ppl = [int(input().strip()) for _ in range(n)]
  4. ppl = sorted(zip((-i for i in ppl), range(n)))
  5. result = [0]*n
  6. task.sort(reverse=True)
  7. for i, j in enumerate(ppl):
  8. result[j[1]] = task[i]
  9. print(*result, sep = "\n")

第四题:单词逆序

对于一个字符串,请设计一个算法,只在字符串的单词间做逆序调整,也就是说,字符串由一些由空格分隔的部分组成,你需要将这些部分逆序。 给定一个原字符串A,请返回逆序后的字符串。例,输入“It’s a dog!”输出“dog! a It’s”
输入描述:输入一行字符串str。(1<=strlen(str)<=10000)
输出描述:返回逆序后的字符串。

示例:

示例一示例二
输入It’s a dog!ABC
输出dog! a It’sABC

分析

本期的大水题竟然放在最后一道,有点出乎意料。实在没啥好分析的,题目给的模板已经把单词按空格分隔成了列表,所以直接把列表翻转,再用空格拼接然后打印出来即可。

参考代码

  1. s = input().strip().split()
  2. print(" ".join(s[::-1]))
本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号