Re: 回国2年了，最近被个安全部美女狂追 (转载) - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

Re: 回国2年了，最近被个安全部美女狂追 (转载)

Re: 回国2年了，最近被个安全部美女狂追 (转载)# Joke - 肚皮舞运动

j*l2010-04-19 07:04

1 楼

是Maximum SubArray Sum的变体,这里有几个要求，一个是连续，一个是最长，一个是
和小于等于一个定值T
假定全部元素的总和是S, 定义U = S - T, 那么试着把这个问题转为等价的补问题: 找
首尾两段，长度加起来最短且其和大于等于U，剩下的中间那截自然就是满足题目的最
长子数组。
有三种情况
1) 只有从首开始的一段
2) 只有以尾结束的一段
3) 首尾两段都有，且不相交
对这三种情况取最小就可以解答
由于首尾两端都是固定的，那么算出那么算出a1...ai的和，以及aj...aN的和，都只要
O(N)时间, 所以1), 2)都是O(N)时间可解的
难办的是3), 据说可以处理一下，用binary search的思想在NlogN解决。想了半天未果
，请帮忙解答，谢谢。

o*92010-04-19 07:04

2 楼

孩子3岁，洗牙的时候发现一颗门牙有轻微蛀牙。牙医约了下次补牙及给牙齿做 x-ray
，做的时候要给孩子用 sedation 和 laughing gas
在网上查了查 sedation，似乎是说一种镇定剂，但诊所给我的注意事项，术前6小时不
能吃喝，术后父母要一刻不离陪伴24小时等等以及描述的孩子可能会有的症状，看地我很害怕。想问
有没有父母知道或孩子用过？

G*a2010-04-19 07:04

3 楼

【以下文字转载自 Love 讨论区】
发信人: Gilda (屠龙公主,好女不跟女斗), 信区: Love
标题: Re: 回国2年了，最近被个安全部美女狂追
发信站: BBS 未名空间站 (Mon Apr 19 14:11:42 2010, 美东)
你知道美帝太多秘密，土共要彻查你：）
脱光了等着被搜身就好！
不能反抗！

m*g2010-04-19 07:04

4 楼

能不能用首尾两个指针head tail
while(tail != end)
{
tail++;
len++;
sum+=array[tail];
while(sum>Max)
{
sum-=array[head];
len--;
}
if(len>maxLen) maxLen=len;
}
基本思想就是反正要连续的，那就全都走一遍呗

g*92010-04-19 07:04

5 楼

门牙6岁就换了，还是轻微蛀牙，
废那个劲干啥。
要我就不做了，最少也等到4岁，懂事了就上点笑气。

ray
我很害怕。想问

【在 o*******9 的大作中提到】

: 孩子3岁，洗牙的时候发现一颗门牙有轻微蛀牙。牙医约了下次补牙及给牙齿做 x-ray
: ，做的时候要给孩子用 sedation 和 laughing gas
: 在网上查了查 sedation，似乎是说一种镇定剂，但诊所给我的注意事项，术前6小时不
: 能吃喝，术后父母要一刻不离陪伴24小时等等以及描述的孩子可能会有的症状，看地我很害怕。想问
: 有没有父母知道或孩子用过？

k*e2010-04-19 07:04

6 楼

公主要屠龙了。

【在 G***a 的大作中提到】

: 【以下文字转载自 Love 讨论区】
: 发信人: Gilda (屠龙公主,好女不跟女斗), 信区: Love
: 标题: Re: 回国2年了，最近被个安全部美女狂追
: 发信站: BBS 未名空间站 (Mon Apr 19 14:11:42 2010, 美东)
: 你知道美帝太多秘密，土共要彻查你：）
: 脱光了等着被搜身就好！
: 不能反抗！

I*g2010-04-19 07:04

7 楼

其实把首尾连起来成个圈就好了

t*12010-04-19 07:04

8 楼

3岁的小孩要做x-ray，我上次听到我们牙医说好像5岁还是6岁才可以做。

G*a2010-04-19 07:04

9 楼

这难道不可疑么？
这难道不是美帝奸细么？
为什么手机后5位，和车牌都能对上？
一定是FBI发牌照的系统错误

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

: 公主要屠龙了。

d*n2010-04-19 07:04

10 楼

1) suppose sum(1->m) >U
2) supoose sum(len-n+1-> len) > U
3) suppose n < m; you can find if there is a shorter path from 1->x and len-
x+1->len with run time O(n) and 1<=x <= n.

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

: 是Maximum SubArray Sum的变体,这里有几个要求，一个是连续，一个是最长，一个是
: 和小于等于一个定值T
: 假定全部元素的总和是S, 定义U = S - T, 那么试着把这个问题转为等价的补问题: 找
: 首尾两段，长度加起来最短且其和大于等于U，剩下的中间那截自然就是满足题目的最
: 长子数组。
: 有三种情况
: 1) 只有从首开始的一段
: 2) 只有以尾结束的一段
: 3) 首尾两段都有，且不相交
: 对这三种情况取最小就可以解答

y*c2010-04-19 07:04

11 楼

小孩的牙比大人的牙要软，蛀牙腐蚀的很快的，一年时间足够腐蚀到牙髓了，那时可不
是简单补补牙就可以了，要么拔掉，要么杀牙髓带牙冠，孩子受的罪更大，钱也花的更
多。

【在 g*********9 的大作中提到】

: 门牙6岁就换了，还是轻微蛀牙，
: 废那个劲干啥。
: 要我就不做了，最少也等到4岁，懂事了就上点笑气。
:
: ray
: 我很害怕。想问

K*g2010-04-19 07:04

12 楼

没有这么复杂吧？大家看这样做有没有问题？
条件 T={连续和小于或等于S}
假设数组是A，长度为N， L(k)表示从A[k]往前推，符合条件T的子数组的长度， s(k)是子数组的
总和。同时保持一个指针P指向该子数组的起始点。
如果s(k-1)+A[k] > S, 则指针P往前移x步使得s(k-1)+A[k]<=S, L(k) = L(k-1)+1-x.
如果s(k-1)+A[k] <= S, 则L(k) = L(k-1)
最后，遍历L，找出最大的长度。
如果要首尾相接的话，那就不在k=N的时候stop，一直到P越过了a[N-1],然后就stop。
Complexity是O(N)还是O（N^2），有更好的解吗？

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

o*92010-04-19 07:04

13 楼

牙医也跟我说不补的话以后会影响到牙根。
3岁孩子能不能做 x-ray 看来我还得问问清楚，谢谢各位。

h*k2010-04-19 07:04

14 楼

你的算法应该是对的，帮你优化以下
两个指针，初始 p_left=0, p_right=0,
if p_right > p_left, sum(p_left,p_right) = sum of A[p_left,...,p_right-1];
if p_right = p_left, sum(p_left,p_right) = 0
step 1:
while ( sum(p_left,p_right) < T || p_right == n )
p_right increase
step 2:
now set A[p_left, p_right-2] is a maximum length set starting from p_left
whose sum <= T; record its length p_right-1-p_left
step 3:
then increase p_left
while( sum(p_left, p_right) > T )
p_left incrase
step 4:
now set A[p_left, p_right-2] i

【在 K******g 的大作中提到】

: 没有这么复杂吧？大家看这样做有没有问题？
: 条件 T={连续和小于或等于S}
: 假设数组是A，长度为N， L(k)表示从A[k]往前推，符合条件T的子数组的长度， s(k)是子数组的
: 总和。同时保持一个指针P指向该子数组的起始点。
: 如果s(k-1)+A[k] > S, 则指针P往前移x步使得s(k-1)+A[k]<=S, L(k) = L(k-1)+1-x.
: 如果s(k-1)+A[k] <= S, 则L(k) = L(k-1)
: 最后，遍历L，找出最大的长度。
: 如果要首尾相接的话，那就不在k=N的时候stop，一直到P越过了a[N-1],然后就stop。
: Complexity是O(N)还是O（N^2），有更好的解吗？

t*o2010-04-19 07:04

15 楼

关于sedation的问题有人回答吗?
我也想知道这个对3，4岁大孩子必要吗？有影响吗？
谢谢

n*a2010-04-19 07:04

16 楼

X-光没啥问题，我家娃更小的时候就照过了

【在 o*******9 的大作中提到】

: 牙医也跟我说不补的话以后会影响到牙根。
: 3岁孩子能不能做 x-ray 看来我还得问问清楚，谢谢各位。

n*a2010-04-19 07:04

17 楼

没看出有啥影响来。当然我家娃是全麻进了手术室，比Sedation要严重哈
有没有必要要问医生吧。你家娃能在清醒的状态下不挣扎，配合医生吗？

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

: 关于sedation的问题有人回答吗?
: 我也想知道这个对3，4岁大孩子必要吗？有影响吗？
: 谢谢