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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3767 天前的主题，其中的信息可能已经有所发展或是发生改变。

有一个长度为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)

特此求教。

列表

花费

购买

28 条回复 • 2014-07-31 12:18:23 +08:00

loryyang

2014-07-30 17:07:32 +08:00

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

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

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

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

mingkaidox

2014-07-30 17:18:51 +08:00 via Android

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

MarioLuisGarcia

2014-07-30 17:31:08 +08:00

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

MarioLuisGarcia

2014-07-30 17:31:36 +08:00

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

MarioLuisGarcia

2014-07-30 18:23:23 +08:00

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

MarioLuisGarcia

2014-07-30 18:37:41 +08:00

我的解法（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

2014-07-30 18:38:43 +08:00

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

MarioLuisGarcia

2014-07-30 18:40:06 +08:00

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

2014-07-30 18:40:27 +08:00

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

MarioLuisGarcia

2014-07-30 18:41:01 +08:00

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

MarioLuisGarcia

2014-07-30 18:41:28 +08:00

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

qsl0913

2014-07-30 18:52:32 +08:00

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

qsl0913

2014-07-30 18:53:18 +08:00

@MarioLuisGarcia markdown

MarioLuisGarcia

2014-07-30 18:56:14 +08:00

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

MarioLuisGarcia

2014-07-30 18:57:11 +08:00

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

MarioLuisGarcia

2014-07-30 19:06:17 +08:00

MarioLuisGarcia

2014-07-30 19:06:36 +08:00

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

MarioLuisGarcia

2014-07-30 19:07:20 +08:00

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

2014-07-30 19:07:48 +08:00

@MarioLuisGarcia ```code```

wudikua

2014-07-30 19:08:46 +08:00

`code`

wudikua

2014-07-30 19:08:54 +08:00

2b了。。。

yxjxx

2014-07-30 19:57:50 +08:00

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

lu18887

2014-07-31 00:31:30 +08:00 via iPhone

@wudikua 别逗！

leafx

2014-07-31 02:18:28 +08:00

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

2014-07-31 10:51:04 +08:00

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

loryyang

2014-07-31 11:21:24 +08:00

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

leafx

2014-07-31 12:08:32 +08:00

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

MarioLuisGarcia

2014-07-31 12:18:23 +08:00

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