Python刷OJ———UVa :10474 Where is the Marble?
想说说自己的想法：其实本人并没有想要投身于ACM竞赛中去的想法。刷题更多是出于一种纯粹的练习目的，并不是特别有目标性地追求什么特定的技术或方法。其中确实解决了一些问题（如能被accept），但其他题目则主要是基于LTE（Long Term Evolution）的相关技术进行了研究与尝试。实在不行了，在网上也实在是难以找到用Python语言实现相关算法的具体代码资源。因此出于个人坚持的原则，在博客中放上了部分算法相关的Python实现代码 purely for sharing and learning purposes, please don't take it too seriously!
题目：
注
Input：
There can be multiple test cases. The total number of test cases is less than 65. Each test case starts with two integers: N, representing the count of marbles, and Q, denoting the number of queries that Mina would issue. The subsequent N lines will contain the numbers etched on each of these N marbles. These marble numbers are not listed in any specific order. Following this, there will be Q queries. It is guaranteed that all input values will be non-negative and no more than 10,000. Input concludes with a test case where both N and Q are zero.
Output：
Output the serial number associated with each test case.
Each test case's serial number should be outputted.
For every query processed, a single line must be generated as part of its response.
The format for each line depends on whether any marble has been marked with its corresponding query number.
Two distinct formatting options are outlined below:
- The first option is to report 'x found at y' when a marble with x is located at position y (positions are numbered from 1 through N).
- The second option indicates that 'x not found' if no marble carrying x exists.
Refer to sample outputs to understand how results should be formatted.
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 中存在，存在和不存在都有对应的输出，见示例
思路 ：
主要涉及两个步骤：排序和查找。通常情况下，默认采用快速排序算法来处理基于有序序列的数据集。具体来说，在每一轮处理中：首先接收全部的数据项；其次进行排序；随后实现二分查找；最后将结果返回。
上代码
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)以下是对原文的改写
由于需要同时对每一个进行二分查找，在调用递归的过程中，每一次递归调用都需要传递一个指针参数（尽管Python中没有传统意义上的指针概念）。这种表述是为了帮助大家更好地理解。
（3）.最初未被递归调用的函数左指针left可以设置为0即可；而对于右指针right，则需根据N列表的长度进行设置。此外还需传递目标Q。在之前我们已将Q整理为一个列表形式，并依据映射规则即可实现相应的功能。
（4）.最初设想中将N设置为默认参数并不奏效
由于默认参数必须是不可变对象 ！而列表是可变对象，在此情况下其长度也是可变的
因此，在全局引用的方法也不可行（因后续需递归操作），于是我决定采用以下策略：初始化一个空列表_right = [] ，并在每次接收Q的同时同步记录N的元素数量。这样就能保证与Q列等长的一致性
而使用map函数则更为合适（若输入多个可变序列，则会自动截断至最短者），因此必须确保right = []与list_Q = []保持一致的长度）
这段代码曾 myself试用过一些网上提供的测试案例体验后发现运行速度相当快速但提交作业却总是会遇到超时的问题后来我又尝试一次性输入了100个测试用例结果明显变慢了许多
也许我的代码还有提升空间, 如果 Python 的小伙伴们有任何建议, 请留言评论.
放一下 UVa的 OJ：https://onlinejudge.org/index.php