菜鸟郁闷了... - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PhotoGear - 摄影器材

菜鸟郁闷了...

菜鸟郁闷了...# PhotoGear - 摄影器材

b*u2010-08-01 07:08

1 楼

原题在
https://www.hackerrank.com/challenges/triplets
There is an integer array d which does not contain more than two elements of
the same value. How many distinct ascending triples (d[i] < d[j] < d[k], i
< j < k) are present?
一开始我用了三重循环，每层用map来去重。结果小case过了，大case超时。
想了下用DP, 两个数组，第一个A[i]存储左边比 d[i]小的个数，第二个B[i]存储右边
比d[i]大的个数，这样如果不考虑重复的话就是 sum of A[i]*B[i]，但是重复的情况
太难搞了

x*22010-08-01 07:08

2 楼

前几天跳了amazon的panasonic G1,今天才知道这个玩意不是单反机...是不是多家200
搞个t1比较合适啊？

x*y2010-08-01 07:08

3 楼

for any number, if there is a duplicate, say at index m, n (mA[m]*B[n] are used twice.

m*72010-08-01 07:08

4 楼

不是单反，胜似单反

i*s2010-08-01 07:08

5 楼

这不就是抄interviewstreet上的么.
下面是我的python code，idea一样，处理重复有一点技巧，你可以自己想想。Time
complexity 应该是O(n^2)，主要花在build smaller, greater array上，不过应该能
做到O(nlogn) on average case。我没仔细想过。
import sys
import bisect
arr_size = int(sys.stdin.readline())
arr = map(int, sys.stdin.readline().split())
smaller_than = [0 for i in range(arr_size)]
greater_than = [0 for i in range(arr_size)]
index_map = {}
for i in range(arr_size):
if arr[i] in index_map:
index_map[arr[i]].append(i)
else:
index_map[arr[i]] = [i]
sorted_arr = []
s = set()
for i in range(arr_size):
if arr[i] not in s:
bisect.insort(sorted_arr, arr[i])
s.add(arr[i])
pos = bisect.bisect_left(sorted_arr, arr[i])
smaller_than[i] = pos
sorted_arr = []
s = set()
for i in reversed(range(arr_size)):
if arr[i] not in s:
bisect.insort(sorted_arr, arr[i])
s.add(arr[i])
pos = bisect.bisect_left(sorted_arr, arr[i])
greater_than[i] = len(s) - pos - 1
result = 0
for indexes in index_map.values():
if len(indexes) == 1:
result += smaller_than[indexes[0]] * greater_than[indexes[0]]
else:
a, b = indexes
result += smaller_than[a] * greater_than[a] + (smaller_than[b] -
smaller_than[a]) * greater_than[b]
print result

of
i

【在 b*****u 的大作中提到】

: 原题在
: https://www.hackerrank.com/challenges/triplets
: There is an integer array d which does not contain more than two elements of
: the same value. How many distinct ascending triples (d[i] < d[j] < d[k], i
: < j < k) are present?
: 一开始我用了三重循环，每层用map来去重。结果小case过了，大case超时。
: 想了下用DP, 两个数组，第一个A[i]存储左边比 d[i]小的个数，第二个B[i]存储右边
: 比d[i]大的个数，这样如果不考虑重复的话就是 sum of A[i]*B[i]，但是重复的情况
: 太难搞了

x*22010-08-01 07:08

6 楼

has the same quality as T1i? except no vedio

【在 m****7 的大作中提到】

: 不是单反，胜似单反

d*02010-08-01 07:08

7 楼

你跟佳能豪华的镜头群无缘了

t*e2010-08-01 07:08

8 楼

不是 same, image quality better than T1i

【在 x*******2 的大作中提到】

: has the same quality as T1i? except no vedio

m*72010-08-01 07:08

9 楼

it's more compact and also with interchangable lens. IQ-wise maybe not as
good as SLRs, but still much better than DCs.

p*y2010-08-01 07:08

10 楼

under dim light(ISO)? sport action (shutter speed)?

【在 t****e 的大作中提到】

: 不是 same, image quality better than T1i

m*72010-08-01 07:08

11 楼

EVIL's ISO is better than low-end DSLRs. but sport action not quite, they
still have shutter delay.

【在 p*******y 的大作中提到】

: under dim light(ISO)? sport action (shutter speed)?

p*y2010-08-01 07:08

12 楼

See here:
http://www.focus-numerique.com/test-90/reflex-panasonic-gh1-test-bruit-electronique-12.html
大小上的差距不是光学能弥补的。就如同稍老的全副还是要比新的半副ISO方面强一样(当然时间不能太久了，否则sensor技术不同导致的差距就其主要作用了)。
总之，我虽然不了解革命机，但不难想象它就是一个画质和体积之间的balance或者说compromise，认清位置，不要拿己之短去挑战彼之长。

【在 m****7 的大作中提到】

: EVIL's ISO is better than low-end DSLRs. but sport action not quite, they
: still have shutter delay.

d*02010-08-01 07:08

13 楼

比T2i强点，但是远不如D5000和KX

【在 m****7 的大作中提到】

: EVIL's ISO is better than low-end DSLRs. but sport action not quite, they
: still have shutter delay.

m*72010-08-01 07:08

14 楼

d5000那个像素密度就别拿来说了

【在 d*****0 的大作中提到】

: 比T2i强点，但是远不如D5000和KX

x*22010-08-01 07:08

15 楼

怎么牛拜？？？那我就先玩这个G1好了

【在 d*****0 的大作中提到】