M**A
发帖数: 78 | 1 Every athlete is characterized by his mass 'm' (in kg) and strength 's' (in
kg). You are to find the maximum number of athletes that can form a tower
standing one upon another. An athlete can hold a tower of athletes with
total mass equal to his strength or less than his strength. Input contains
the number of athletes n and their parameters. These inputs can be assumed
to be passed as arguments (Integer n and List> parameterList) appropriate
for your language of choice: For example:
n m1 s1 m2 s2 ... mn sn If mi > mj then si > sj, but athletes with equal
masses can be of different strength. Number of athletes n < 100000. Masses
and strengths are positive integers less than 2000000.
For example: Input #1： 4 3 4 2 2 7 6 4 5
Would yield Output #1： 3
https://github.com/fabiensanglard/Pyramid
搭人梯 7 6 = 3 4 + 2 2 或者 2 2 + 4 5 共3个人
除了brute force, 各位朋友有何高见？ |
f*****e
发帖数: 2992 | 2 Greedy吧，
先找重量最轻的，记为m1
然后找min(m_i) where si>m1
然后找min(m_i) where si>m1 + m2
然后找min(m_i) where si>m1 + m2 + m3
in
【在 M**A 的大作中提到】
: Every athlete is characterized by his mass 'm' (in kg) and strength 's' (in
: kg). You are to find the maximum number of athletes that can form a tower
: standing one upon another. An athlete can hold a tower of athletes with
: total mass equal to his strength or less than his strength. Input contains
: the number of athletes n and their parameters. These inputs can be assumed
: to be passed as arguments (Integer n and List> parameterList) appropriate
: for your language of choice: For example:
: n m1 s1 m2 s2 ... mn sn If mi > mj then si > sj, but athletes with equal
: masses can be of different strength. Number of athletes n < 100000. Masses
: and strengths are positive integers less than 2000000.
|
c**s
发帖数: 159 | |
l***i
发帖数: 1309 | 4 why not sort by strength? |
p*****2
发帖数: 21240 | 5 sort by m and s then dp
【在 M**A 的大作中提到】
: Every athlete is characterized by his mass 'm' (in kg) and strength 's' (in
: kg). You are to find the maximum number of athletes that can form a tower
: standing one upon another. An athlete can hold a tower of athletes with
: total mass equal to his strength or less than his strength. Input contains
: the number of athletes n and their parameters. These inputs can be assumed
: to be passed as arguments (Integer n and List> parameterList) appropriate
: for your language of choice: For example:
: n m1 s1 m2 s2 ... mn sn If mi > mj then si > sj, but athletes with equal
: masses can be of different strength. Number of athletes n < 100000. Masses
: and strengths are positive integers less than 2000000.
|
F********9
发帖数: 44 | 6 LZ这是招人做家庭作业的吧。
我之前申A时，这道题是家庭作业，做完发给recruiter的。
on site 时，有个面试官想出这道题，我直接说，这是A的家庭作业， 给否了。
祝你好运。 |
p*****2
发帖数: 21240 | 7
这题有OJ吗？
【在 F********9 的大作中提到】
: LZ这是招人做家庭作业的吧。
: 我之前申A时，这道题是家庭作业，做完发给recruiter的。
: on site 时，有个面试官想出这道题，我直接说，这是A的家庭作业， 给否了。
: 祝你好运。
|
t****a
发帖数: 1212 | 8 确定么？这个例子
m s
1 6
2 3
3 0
如果按照m从小到大排序后dp结果是((1 6) (2 3))
从大到小排序后dp结果是 ((3 0) (2 3) (1 6))
【在 p*****2 的大作中提到】
: sort by m and s then dp
|
p*****2
发帖数: 21240 | 9
你miss了一个重要条件。
这题有点greedy＋dp的意思。呵呵。
【在 t****a 的大作中提到】
: 确定么？这个例子
: m s
: 1 6
: 2 3
: 3 0
: 如果按照m从小到大排序后dp结果是((1 6) (2 3))
: 从大到小排序后dp结果是 ((3 0) (2 3) (1 6))
|
