move free 5off 胖子有人要吗 (转载) - 未名空间MITBBS历史存档

move free 5off 胖子有人要吗 (转载)# PennySaver - 省钱一族

b*m2010-03-09 08:03

1 楼

1：给一个hashset, 有insert search delete 接口，现在一个ttl(time to live）
的功能
1：假设存数据的每个数据的expire time是相同的，这个简单，做出来了，
2：如果每个数据的expire time不同，该用什么样式的数据结构，怎么实现
2：空间有很多固定点，找出距离当前位置距离最近的 k个点，时间复杂度尽量少
3：有n个东西每个东西的size不同，现在放到大小固定的框中，问如果放，使得用到
的框最少

b*n2010-03-09 08:03

2 楼

【以下文字转载自 Rite_aid 俱乐部】
发信人: beelin (beelin), 信区: Rite_aid
标题: move free 5off 胖子有人要吗
发信站: BBS 未名空间站 (Tue Mar 9 12:30:49 2010, 美东)
ebay买的，买20张，实际只需要6～10张。
所以送10张。赏赐几个包子就太好了。
zip code 10029
邮寄也可。不过请paypal给我邮费。

f*t2010-03-09 08:03

3 楼

这不三道题么…第三题bin packing难度碉堡了

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

: 1：给一个hashset, 有insert search delete 接口，现在一个ttl(time to live）
: 的功能
: 1：假设存数据的每个数据的expire time是相同的，这个简单，做出来了，
: 2：如果每个数据的expire time不同，该用什么样式的数据结构，怎么实现
: 2：空间有很多固定点，找出距离当前位置距离最近的 k个点，时间复杂度尽量少
: 3：有n个东西每个东西的size不同，现在放到大小固定的框中，问如果放，使得用到
: 的框最少

b*n2010-03-09 08:03

4 楼

可以麻烦已经给我站内信的tx门跟贴告诉我要几张吗？先到先得。
估计已经不够了。其他人不用跟了
不用邮寄是说，如果你住得很近，pick up也行。。。

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

: 【以下文字转载自 Rite_aid 俱乐部】
: 发信人: beelin (beelin), 信区: Rite_aid
: 标题: move free 5off 胖子有人要吗
: 发信站: BBS 未名空间站 (Tue Mar 9 12:30:49 2010, 美东)
: ebay买的，买20张，实际只需要6～10张。
: 所以送10张。赏赐几个包子就太好了。
: zip code 10029
: 邮寄也可。不过请paypal给我邮费。

w*t2010-03-09 08:03

5 楼

1.2 如果每个数据的expire time不同，该用什么样式的数据结构，怎么实现
可以考虑优先队列，每个数据进来后，可以根据expire time算出结束的时间戳，将 {
exp_time, data} 放入优先队列中，然后定时check队列的头部元素，时间到了就pop，
并delete(data).

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

: 1：给一个hashset, 有insert search delete 接口，现在一个ttl(time to live）
: 的功能
: 1：假设存数据的每个数据的expire time是相同的，这个简单，做出来了，
: 2：如果每个数据的expire time不同，该用什么样式的数据结构，怎么实现
: 2：空间有很多固定点，找出距离当前位置距离最近的 k个点，时间复杂度尽量少
: 3：有n个东西每个东西的size不同，现在放到大小固定的框中，问如果放，使得用到
: 的框最少

b*n2010-03-09 08:03

6 楼

3.31 过期。但是这个星期拿rain check的话，还是可以在过期前用上的。

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

: 可以麻烦已经给我站内信的tx门跟贴告诉我要几张吗？先到先得。
: 估计已经不够了。其他人不用跟了
: 不用邮寄是说，如果你住得很近，pick up也行。。。

j*y2010-03-09 08:03

7 楼

1.2, 是不是可以用一个 max heap ? key 就是每个数据的 ttl = current time
stamp + expire time.

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

: 1：给一个hashset, 有insert search delete 接口，现在一个ttl(time to live）
: 的功能
: 1：假设存数据的每个数据的expire time是相同的，这个简单，做出来了，
: 2：如果每个数据的expire time不同，该用什么样式的数据结构，怎么实现
: 2：空间有很多固定点，找出距离当前位置距离最近的 k个点，时间复杂度尽量少
: 3：有n个东西每个东西的size不同，现在放到大小固定的框中，问如果放，使得用到
: 的框最少

l*i2010-03-09 08:03

8 楼

为什么不是min heap？

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

: 1.2, 是不是可以用一个 max heap ? key 就是每个数据的 ttl = current time
: stamp + expire time.

r*h2010-03-09 08:03

9 楼

求第三题的思路，完全没头绪啊

c*t2010-03-09 08:03

10 楼

应该是min heap吧。
第三题，以前想过一次，没想出来怎么做。

【在 l****i 的大作中提到】

: 为什么不是min heap？

Q*s2010-03-09 08:03

11 楼

第三题就是背包问题

j*y2010-03-09 08:03

12 楼

能给出状态方程吗？
背包九讲里面没这个阿

【在 Q****s 的大作中提到】

: 第三题就是背包问题

p*p2010-03-09 08:03

13 楼

第三题greedy对么，对于当前的bin，找放进去以后剩余空间最少的那个，如果没有，
就新开一个
O(n^2)

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

: 1：给一个hashset, 有insert search delete 接口，现在一个ttl(time to live）
: 的功能
: 1：假设存数据的每个数据的expire time是相同的，这个简单，做出来了，
: 2：如果每个数据的expire time不同，该用什么样式的数据结构，怎么实现
: 2：空间有很多固定点，找出距离当前位置距离最近的 k个点，时间复杂度尽量少
: 3：有n个东西每个东西的size不同，现在放到大小固定的框中，问如果放，使得用到
: 的框最少

j*y2010-03-09 08:03

14 楼

poj有道这样的题是用 greedy,不过那里的例子简单多了
http://poj.org/problem?id=1017

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

: 第三题greedy对么，对于当前的bin，找放进去以后剩余空间最少的那个，如果没有，
: 就新开一个
: O(n^2)