最近了解到Google Code Jam这件事情，一个编程竞赛项目，登录之后可以看到以前的题目，觉得都很有意思，于是想尝试一下。
我看到的第一题是Store Credit，大概意思就是给你一定数额的钱，然后给你一个物品价格清单，选择两个物品，正好花完所有的钱。具体内容可以参考http://code.google.com/codejam/contest/351101/dashboard#s=p0
因为要求正好花完所有的钱，贪心算法就不太管用了，还好只是要求选择两个物品，直接的方法就是遍历搜索了。确定一个物品，查找另一个价格满足要求的物品。在遍历搜索中，也有一些地方可以减少搜索次数。
比如，顺序遍历物品，选定一个物品之后，只需要在剩余的物品中遍历查找。
再比如，先将物品按价格排序，可以将价格等于大于总钱数的物品排除在搜索范围之外。需要注意的是，排序的时候需要记录物品对应的顺序，因为它要求输出物品的原始序号。
确定了这些，开始写程序了。学习了那么久的Python，几乎还没有正式写过程序，所以决定用Python来实现。
先是排序的函数，使用快速排序算法，
参考http://en.wikipedia.org/wiki/Quicksort，那里Python写的程序很简单，但是没有记录原始序号，还是得自己写一个。
代码如下，
#!/usr/bin/python
#encoding:UTF-8
#Filename:QuickSort.py
def partition(A,B,p,r):
x = A[r]
i = p-1
for j in range(p,r):
if A[j]<=x:
i = i + 1
A[i],A[j] = A[j],A[i]
B[i],B[j] = B[j],B[i]
A[i+1],A[r] = A[r],A[i+1]
B[i+1],B[r] = B[r],B[i+1]
return i+1
def quickSort(A,B,p,r):
if p<r:
q = partition(A,B,p,r)
quickSort(A,B,p,q-1)
quickSort(A,B,q+1,r)
在排序之后，查找使用的是二分查找，
代码如下，
#!/usr/bin/python
#encoding:UTF-8
#Filename:BinarySearch.py
def binarySearch(A,x,lo,hi):
res = -1
while(lo<=hi):
mid = (lo+hi) / 2
if x==A[mid]:
res = mid
break
elif x<A[mid]:
hi = mid - 1
else:
lo = mid + 1
return res
然后写了一个solver程序，一种是直接搜索，另一种是先排序后搜索，
代码如下，
#!/usr/bin/python
#encoding:UTF-8
#Filename:CreditSolver.py
import QuickSort
import BinarySearch
def creditSolverDirect(m,l,p):
an = [0,0]
for i in range(l-1):
for j in range(i+1,l):
if p[i]+p[j]==m:
an = [i+1,j+1]
return an
return an
def creditSolverSort(m,l,p):
an = [0,0]
pa = p;
pb = range(0,l)
QuickSort.quickSort(pa,pb,0,l-1)
i = 0;
for price in pa:
i = i+1
if price < m:
res = BinarySearch.binarySearch(pa,m-price,i,l-1)
if res!=-1:
an = [pb[i-1],pb[res]]
break
if an[0]>an[1]:
an[0],an[1] = an[1],an[0]
an = [an[0]+1,an[1]+1]
return an
最后就是主程序，读取输入，解题，输出写入文件，
代码如下，
#!/usr/bin/python
#Filename: StoreCredit.py
import CreditSolver
# read file
linenum = 0;
testCaseNum = 0;
caseLines = 3;
fin = open("input.txt")
fout = open("output.txt","w")
# to process first line, test case number
line = fin.readline()
if not line:
print "failed to open input.txt"
linenum = linenum + 1
testCaseNum = int(line)
#print "test cases number:%d" %(testCaseNum)
for i in range(testCaseNum):
money = int(fin.readline())
items = int(fin.readline())
priceStr = fin.readline().split(" ");
price = [int(stri) for stri in priceStr]
# print "--- to solve case %d ---" %(i)
# print "money:%d" %(money)
# print "items:%d" %(items)
# print "price:"
# print price
L = [0,0]
if items > 128:
L = CreditSolver.creditSolverSort(money,items,price)
else:
L = CreditSolver.creditSolverDirect(money,items,price)
answer = ""
if L[1]!=0:
answer = "Case #" + str(i) + ": " + str(L[0]) + " " + str(L[1]) + "\n"
else:
answer = "Case #" + str(i) + ": x\n"
fout.write(answer)
#print "done!"
fin.close()
fout.close()
对于题目中给的测试情况，输出是正确的，没有测试过更大的例子，不知道是否会出现异常，或者性能很差。如果谁发现了问题，希望能告诉我，大家也可以一起改进解题过程和程序的实现。