一个在实际工作中遇到的算法问题，比较基础，求教。

[MarioLuisGarcia]

有一个长度为n的列表，代表某物品的价格。

玩家第一次购买该物品时，花费的价格是列表第一项的价格。依此类推，到第n次，花费的是列表第n项的价格。

从第n+1次开始，每次购买花费的都是列表第n项的价格。

在一个购买行为里，玩家可以购买多项该物品，如，购买次数为3。如该玩家是首次购买该物品，所花费的钱是列表第1,2,3项的总和。 如玩家在进行该购买行为时，已经买过n次了，那么该购买行为花费的金钱是3*n。

现在我们仅知道玩家一个购买行为里的购买次数x （不知道他之前买了多少次), 以及该购买所花费的金钱y. 我们需要求出该玩家这个购买行为里所花费的金钱组成（第一个购买次数花了多少钱，第二个花了多少钱，第x个购买次数花了多少钱）。

我已经想出应该怎么做，先看 x * 列表第n项 是否等于 y, 如果不等于，再看 (x-1) * 列表第n项 + 1 * 列表第n-1项 是否等于 y, 一直到 1* 列表第x项 + 1 * 列表第x-1项 + ... + 列表第1项 是否等于 y 即可

但是，发现要把这个想法表达成程序语言表达式，对我而言有些困难（用的python)

特此求教。

[loryyang]

除了遍历，其他无解吧。我的第一感觉是这样：

1. 对于固定的购买次数x，我们只需要过一轮数据，就可以知道起点为i的x次购买总价格是多少，也就是一个[i, y]对，i从0到n
2. 那么对于某个固定的y，从1的结果里面找到匹配项就行了。ps：匹配项可能会多于一个，这也是我感觉只能遍历的原因。

复杂度最简单是n*x，当然，你第一步可以稍微优化下，大概是个n+x的复杂度

想的不是很细致，LZ可以再看看

[mingkaidox]

这个可能有多解，比如当第n次和第n-1次买价格一样的时候，可能要注意下。

[MarioLuisGarcia]

@loryyang 怎么解大概想出来了，语言表达还在想。不过在提出这个问题后又狂想一阵，有个雏形了，测试中

[MarioLuisGarcia]

@mingkaidox 为什么会有多解的情况？不是很明白。

[MarioLuisGarcia]

@loryyang 好像可以实现了，不过方法有点dirty....

[MarioLuisGarcia]

我的解法（X = 次数,Y = 钱, L = 列表，写法是python)

T = 0
while True:
if X > T and T ==0:
if L[-1]*(X-T) == Y:
break
else:
T += 1
elif X > T and T >=1:
if L[-1]*(X-T) + sum(L[(-1)-i] for i in xrange(T+1) if i > 0):
break
else:
T += 1
elif X <= T:
if sum(L[(-1)-i] for i in xrange(T-X,T+1) ) == Y:
break
else:
T += 1

[MarioLuisGarcia]

indentation因为v2ex显示问题不对了。

[MarioLuisGarcia]

T = 0
while True:
if X > T and T ==0:
if L[-1]*(X-T) == Y:
break
else:
T += 1
elif X > T and T >=1:
if L[-1]*(X-T) + sum(L[(-1)-i] for i in xrange(T+1) if i > 0):
break
else:
T += 1
elif X <= T:
if sum(L[(-1)-i] for i in xrange(T-X,T+1) ) == Y:
break
else:
T += 1

[MarioLuisGarcia]

再试一次排版，还是失败了。。。

[MarioLuisGarcia]

T = 0
while True:
\ if X > T and T ==0:

[MarioLuisGarcia]

看来有点弄不明白怎么在v2ex 缩进了。。。。

[qsl0913]

L=[1,2,3,4,5,5,4,3,2,1,1,1,1]
X=5
Y=15
两个解

[qsl0913]

@MarioLuisGarcia markdown

[MarioLuisGarcia]

@qsl0913 看来md的学习优先度要提前了.
如果列表是递增的，即后一项一定大于或等于前一项，应该就不会出现你所说的情况了吧？

[MarioLuisGarcia]

@qsl0913 oh my god, 难道我要用&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;来缩进代码？ @天！

[MarioLuisGarcia]

T = 0
while True:
if X > T and T ==0:
if L[-1]*(X-T) == Y:
break
else:
T += 1
elif X > T and T >=1:
if L[-1]*(X-T) + sum(L[(-1)-i] for i in xrange(T+1) if i > 0):
break
else:
T += 1
elif X <= T:
if sum(L[(-1)-i] for i in xrange(T-X,T+1) ) == Y:
break
else:
T += 1

[MarioLuisGarcia]

...从stackoverflow辅助过来也不行。。。

[MarioLuisGarcia]

T = 0
while True:
* if X > T and T ==0:
* if L[-1]*(X-T) == Y:
* break
*else:
* T += 1
* elif X > T and T >=1:
* if L[-1]*(X-T) + sum(L[(-1)-i] for i in xrange(T+1) if i > 0):
* break
*else:
* T += 1
* elif X <= T:
* if sum(L[(-1)-i] for i in xrange(T-X,T+1) ) == Y:
* break
*else:
* T += 1

[wudikua]

@MarioLuisGarcia ```code```

[wudikua]

`code`

[wudikua]

2b了。。。

[yxjxx]

@MarioLuisGarcia gist吧，v2目前不支持md呢

[lu18887]

@wudikua 别逗！

[leafx]

n= [4, 3, 2, 1]
x= 2
y= 13
so:
1. *2+ *3 = (4+3) + (2*3) = y(13)
2. *1+ *3 = 4 + (3*3) = y(13)
--------------------------------------------------------
希望你能理解我的用意，虽然概率小点，但是确实存在这样的情况

[MarioLuisGarcia]

@leafx x = 2， y 为什么会等于 13？ x 是表示购买的次数啊，一次只会花1次钱。x=2 , y最大是8呀。。

[loryyang]

@MarioLuisGarcia 额，这个我也说不好，你多想想这种问题，慢慢的就会有解决思路了。思维是锻炼出来的。如果你觉得说不清楚，写伪代码即可，这个在程序员中间到不是最主要的问题

[leafx]

@MarioLuisGarcia 是啊， X表示的购买次数，第一次买2项物品，第二次买3项物品，好像符合你的逻辑额

[MarioLuisGarcia]

@leafx y表示的是x次购买所花费的钱。。。