1
loryyang 2014-07-30 17:07:32 +08:00 1
除了遍历,其他无解吧。我的第一感觉是这样:
1. 对于固定的购买次数x,我们只需要过一轮数据,就可以知道起点为i的x次购买总价格是多少,也就是一个[i, y]对,i从0到n 2. 那么对于某个固定的y,从1的结果里面找到匹配项就行了。ps:匹配项可能会多于一个,这也是我感觉只能遍历的原因。 复杂度最简单是n*x,当然,你第一步可以稍微优化下,大概是个n+x的复杂度 想的不是很细致,LZ可以再看看 |
2
mingkaidox 2014-07-30 17:18:51 +08:00 via Android 1
这个可能有多解,比如当第n次和第n-1次买价格一样的时候,可能要注意下。
|
3
MarioLuisGarcia OP @loryyang 怎么解大概想出来了,语言表达还在想。不过在提出这个问题后又狂想一阵,有个雏形了,测试中
|
4
MarioLuisGarcia OP @mingkaidox 为什么会有多解的情况?不是很明白。
|
5
MarioLuisGarcia OP @loryyang 好像可以实现了,不过方法有点dirty....
|
6
MarioLuisGarcia OP 我的解法(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 |
7
MarioLuisGarcia OP indentation因为v2ex显示问题不对了。
|
8
MarioLuisGarcia OP 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 |
9
MarioLuisGarcia OP 再试一次排版,还是失败了。。。
|
10
MarioLuisGarcia OP T = 0
while True: \ if X > T and T ==0: |
11
MarioLuisGarcia OP 看来有点弄不明白怎么在v2ex 缩进了。。。。
|
12
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 两个解 |
13
qsl0913 2014-07-30 18:53:18 +08:00
@MarioLuisGarcia markdown
|
14
MarioLuisGarcia OP @qsl0913 看来md的学习优先度要提前了.
如果列表是递增的,即后一项一定大于或等于前一项,应该就不会出现你所说的情况了吧? |
15
MarioLuisGarcia OP @qsl0913 oh my god, 难道我要用 来缩进代码? @天!
|
16
MarioLuisGarcia OP 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 |
17
MarioLuisGarcia OP ...从stackoverflow辅助过来也不行。。。
|
18
MarioLuisGarcia OP 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 |
19
wudikua 2014-07-30 19:07:48 +08:00
@MarioLuisGarcia ```code```
|
20
wudikua 2014-07-30 19:08:46 +08:00
`code`
|
21
wudikua 2014-07-30 19:08:54 +08:00
2b了。。。
|
22
yxjxx 2014-07-30 19:57:50 +08:00
@MarioLuisGarcia gist吧,v2目前不支持md呢
|
24
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) -------------------------------------------------------- 希望你能理解我的用意,虽然概率小点,但是确实存在这样的情况 |
25
MarioLuisGarcia OP @leafx x = 2, y 为什么会等于 13? x 是表示购买的次数啊,一次只会花1次钱。x=2 , y最大是8呀。。
|
26
loryyang 2014-07-31 11:21:24 +08:00
@MarioLuisGarcia 额,这个我也说不好,你多想想这种问题,慢慢的就会有解决思路了。思维是锻炼出来的。如果你觉得说不清楚,写伪代码即可,这个在程序员中间到不是最主要的问题
|
27
leafx 2014-07-31 12:08:32 +08:00
@MarioLuisGarcia 是啊, X表示的购买次数,第一次买2项物品,第二次买3项物品,好像符合你的逻辑额
|
28
MarioLuisGarcia OP @leafx y表示的是x次购买所花费的钱。。。
|