急问：continental还是delta，还是卖了点数？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Money - 海外理财

急问：continental还是delta，还是卖了点数？

急问：continental还是delta，还是卖了点数？# Money - 海外理财

B*p2011-09-28 07:09

1 楼

1st edition section 7.7 no. 6, 2nd edition, section 7.7, no. 12
After the array x[0,,N-1] is initialized to zero. N of the following
operations are performed
for i = L to U do
x[i] += V;
where L, U and V are parameters of each operation (L and U are integers
satisfying 0<=L<=Ureal). After the N operations, the values of x[0] through x[N-1] are
reported in order. The method just
sketched requires O(N^2) time. Can you find a faster algorithm?
1. What is the value of L and U for e

l*t2011-09-28 07:09

2 楼

查了账户，发现自己也得了40k miles，真高兴啊。。。可是我这儿continental的航线
很少，有也很贵或是要几个stops，倒是delta还行。。。看班上的讨论都不建议转
delta，真是纠结。。。
另外由于娃还小，近年旅行不会太多，最多回一下国，也得1年半以后吧，我这种情况
是不是应该把点数去二手卖了？

Z*Z2011-09-28 07:09

3 楼

be
different
I think L and U are fixed for N operations.
The values of X[1] through X[N] is reported in order does not mean X is
sorted.

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

: 1st edition section 7.7 no. 6, 2nd edition, section 7.7, no. 12
: After the array x[0,,N-1] is initialized to zero. N of the following
: operations are performed
: for i = L to U do
: x[i] += V;
: where L, U and V are parameters of each operation (L and U are integers
: satisfying 0<=L<=U: real). After the N operations, the values of x[0] through x[N-1] are
: reported in order. The method just
: sketched requires O(N^2) time. Can you find a faster algorithm?

d*g2011-09-28 07:09

4 楼

卖了...

K*g2011-09-28 07:09

5 楼

If L and U are fixed, then the question should be very easy. The complexity
will be O(N). Then what is the point of this problem?

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

:
: be
: different
: I think L and U are fixed for N operations.
: The values of X[1] through X[N] is reported in order does not mean X is
: sorted.

l*t2011-09-28 07:09

6 楼

谢谢！

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

: 卖了...

b*h2011-09-28 07:09

7 楼

After the N operations, the values of x[0] through x[N-1] are
The above words doesn't mean x[] is sorted. It just says after those N
operations, you are going to report the values in order. It doesn't matter
how are you going to do it. And it has nothing to do with the previously
described process.
The intent of this problem is asking you to give an algorithm that simulates
the described process in complexity less than O(N^2).

g*n2011-09-28 07:09

8 楼

你那里delta还行就转delta呗，又不过期，现在转还有bonus

z*o2011-09-28 07:09

9 楼

我觉得 L, U 在不同时候是不同的，否则
否则 s = sum(V) 然后 for i = L to V do x[i] = v * N 就可以了
既然说 L, U, V are parameters of each operation, 我觉得他们就是每次可以不同
，否则为啥叫 parameters.
这个应该有 NlogN 的算法
把 L,U 看作一个线段，对所有的线段端点（2N个）排序，
s=0
从左到有扫描端点
如果遇到一个左端点，s+=线段对应的v
如果遇到一个右端点，s-=线段对应的v
处理完一个端点后，s就是x[这个端点+1]到x[下一个端点]的值

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