Python刷OJ———UVa :10474 Where is the Marble?

首先说一下，本人没有投身ACM的想法，刷题完全是当练习，有些题能accept，其余基本都是LTE。。讲真的，全网太难找到用python实现的代码了，而我就是如此倔强，于是放一些题的代码在博客上，纯属爱好，大家不要当真哈哈哈哈。
————————————————————————————————————————————

题目：

Raju and Meena love to play with Marbles. They have got a lot of
marbles with numbers written on them. At the beginning, Raju would
place the marbles one after another in ascending order of the numbers
written on them. Then Meena would ask Raju to find the first marble
with a certain number. She would count 1…2…3. Raju gets one point
for correct answer, and Meena gets the point if Raju fails. After some
fixed number of trials the game ends and the player with maximum
points wins. Today it’s your chance to play as Raju. Being the smart
kid, you’d be taking the favor of a computer. But don’t underestimate
Meena, she had written a program to keep track how much time you’re
taking to give all the answers. So now you have to write a program,
which will help you in your role as Raju.

Input：

There can be multiple test cases. Total no of test cases is less than 65. Each test case consists begins with 2 integers: N the number of marbles and Q the number of queries Mina would make. The next N lines would contain the numbers written on the N marbles. These marble numbers will not come in any particular order. Following Q lines will have Q queries. Be assured, none of the input numbers are greater than 10000 and none of them are negative. Input is terminated by a test case where N = 0 and Q = 0

Output：

For each test case output the serial number of the case.
For each of the queries, print one line of output. The format of this line will depend upon whether
or not the query number is written upon any of the marbles. The two different formats are described
below:
• ‘x found at y’, if the first marble with number x was found at position y. Positions are numbered
1, 2, . . . , N.
• ‘x not found’, if the marble with number x is not present.
Look at the output for sample input for details.

Sample Input
4 1
2
3
5
1
5
5 2
1
3
3
3
1
2
3
0 0
Sample Output
CASE# 1:
5 found at 4
CASE# 2:
2 not found
3 found at 3
————————————————————————————————————————————
大体意思就是先给一个整数 N 和 Q ，接下来将会再给 N 个整数，然后你要把他们从小到大排序。然后再给你 Q 个整数，让你找这 Q 个整数是否在 N 中存在，存在和不存在都有对应的输出，见示例

思路：
一个排序，一个查找。排序的话一般快排就可以，既然是有序数列，那肯定是二分法查找
我自己的想法是，对于每一组数据，先把 N 个数和 Q 个数全都接收完（用列表）。然后排序，写一个二分查找的函数。然后用map（）直接并行找所有 Q 中的数。最后将返回结果输出即可。

上代码

from sys import stdin, setrecursionlimit

setrecursionlimit(1000000)

# 前三个函数是快排的代码
def quick_sort(L):
    return q_sort(L, 0, len(L) - 1)


def q_sort(L, left, right):
    if left < right:
        pivot = Partition(L, left, right)

        q_sort(L, left, pivot - 1)
        q_sort(L, pivot + 1, right)
    return L


def Partition(L, left, right):
    pivotkey = L[left]

    while left < right:
        while left < right and L[right] >= pivotkey:
            right -= 1
        L[left] = L[right]
        while left < right and L[left] <= pivotkey:
            left += 1
        L[right] = L[left]

    L[left] = pivotkey
    return left

# 这个函数是二分查找
def find_position(_q, right, left=0):
    mid = int((right + left) / 2)
    if left > right:
        return "{} not found".format(_q)
    elif list_N[mid] == _q:
        posi = mid
        while list_N[posi - 1] == _q:
            posi -= 1
        return "{} found at {}".format(_q, posi + 1)
    elif list_N[mid] > _q:
        return find_position(_q, mid - 1, left)
    else:
        return find_position(_q, right, mid + 1)


list_N = []
list_Q = []
_right = [] # 为了使用map，下文会解释
number = 1
while True:
    N, Q = map(int, stdin.readline().split(' '))
    if N == 0 and Q == 0:
        break
    length = N - 1
    print("CASE# {}:".format(number))
    number += 1
    for l in range(N):
        list_N.append(int(stdin.readline()))
    list_N = quick_sort(list_N)
    for h in range(Q):
        _right.append(length)
        list_Q.append(int(stdin.readline()))
    result = map(find_position, list_Q, _right)
    for re in result:
        print(re)

说一下代码：
（1）.首先，以上快排和二分查找的代码都是按照c的风格来写的，都是在原数组上进行的操作，并没有像网上很多伪代码。。狂建新数组，内存爆炸不说还慢。然后二分查找递归，有待测试数据会递归很深，需要import sys修改一下上限

（2）.因为要同时使用二分查找每一个，众所周知二分查找在调用递归时，每次都需要传入指针（当然其实python中没有指针这样的概念，这样说只是便于大家理解）

（3）.最初的未被递归的函数左指针 left 我们传入0就好
但是对于右指针 right ，需要根据 N 列表的长度来定。而同时，我们还需要传入要寻找的 Q 。在之前我们已经把 Q 收集为一个列表了，根据 map 的映射规则很好实现。

（4）.一开始对于 N ，我想的是用一个默认参数，但是发现不行
因为默认参数必须是不可变量！而列表是可变量，所以它的长度也是可变量
而如果直接global 全局，因为接下来要递归，所以这显然是不行的，于是。。我的办法是，建一个列表_right = [] ，然后每次接收 Q 的时候，顺便也把 N 列表的长度加进去一次，于是就有两个相同长度的列表。
而map（）是可以，和多个列表映射的（但是如果列表长度不一样，会自动按最短的截取。。所以_right = [] 必须和list_Q = []一样长）

（5）.这段代码我自己试过一些网上提供的测试数据，感觉运行起来还是挺快的。但是提交会超时，后来我尝试同时输入100组测试数据，真的是肉眼可见的慢。。。。

当然也可能是我的代码又可以改进的地方，如果python的小伙伴们有什么见解，可以留言评论告诉我

放一下 UVa的 OJ：https://onlinejudge.org/index.php

最后

以上就是典雅小土豆为你收集整理的Python刷OJ———UVa :10474 Where is the Marble?的全部内容，希望文章能够帮你解决Python刷OJ———UVa :10474 Where is the Marble?所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。