v*******C
发帖数: 28 | 1 有N个数，初始值为0， 在M个操作之后，找出最大值。 每个操作(a, b, k)表示给第a
个到第b个数分别加k。
比如说，
N=5， M= 3, 三组(a,b,k)分别是
2, 3, 100;
1, 2, 200;
4, 5, 100;
返回最大值为300.
我只能想到很naive的方法，请教版上大神们有没有更好的方法？先谢谢啦！ | n*******s
发帖数: 17267 | 2 直觉就是每次把index a->b的加K， 最后再选个最大数就可以了。 | C****t
发帖数: 53 | 3 有点像最少会议室问题…不过现在不是按照起点时间排序，是所有的端点排序，左端点
正值，右端点正的相反数。从左到右，记录和的最大值… | v*******C
发帖数: 28 | 4 不好意思，刚没说清楚，K是大于0的不定的数。
【在 n*******s 的大作中提到】
: 直觉就是每次把index a->b的加K， 最后再选个最大数就可以了。
| v*******C
发帖数: 28 | 5 大神，能展开说说吗？不是很理解。。。
【在 C****t 的大作中提到】
: 有点像最少会议室问题…不过现在不是按照起点时间排序，是所有的端点排序，左端点
: 正值，右端点正的相反数。从左到右，记录和的最大值…
| n*******s
发帖数: 17267 | 6 改了， 呵呵， 其实就是问你怎么找最大数吧？
或许需要改进一下， 只需要搜索最小的a和最大的b之间就可以了， 还需要改善的话，
就已经不是年老色衰的人能想明白的了。
【在 v*******C 的大作中提到】
: 不好意思，刚没说清楚，K是大于0的不定的数。
| n*******s
发帖数: 17267 | 7 好像是说把[a, b]排序， 纪录当前最大值， 然后向右滑， 最后返回最大值。
【在 v*******C 的大作中提到】
: 大神，能展开说说吗？不是很理解。。。
| C****t
发帖数: 53 | 8 sort array [(2,100), (3,-100), (1,200), (2,-200), (4,100), (5,-100)]
according to keys(point). if two keys are identical, put ( , +) in front
of (, -). Scan the sorted array, record the sum of values, return the
maximum... M*log(M)
a
【在 v*******C 的大作中提到】
: 有N个数，初始值为0， 在M个操作之后，找出最大值。 每个操作(a, b, k)表示给第a
: 个到第b个数分别加k。
: 比如说，
: N=5， M= 3, 三组(a,b,k)分别是
: 2, 3, 100;
: 1, 2, 200;
: 4, 5, 100;
: 返回最大值为300.
: 我只能想到很naive的方法，请教版上大神们有没有更好的方法？先谢谢啦！
| s****a
发帖数: 794 | 9 你的这个m可和输入个数没啥关系了。。。
【在 C****t 的大作中提到】
: sort array [(2,100), (3,-100), (1,200), (2,-200), (4,100), (5,-100)]
: according to keys(point). if two keys are identical, put ( , +) in front
: of (, -). Scan the sorted array, record the sum of values, return the
: maximum... M*log(M)
:
: a
| s****a
发帖数: 794 | 10 naive的做法是插入O(N)查询O(N)
如果用线段树或者BIT插入O(logN) 查询O(N) 好像也没啥别的办法了 | | | v*******C
发帖数: 28 | 11 多谢大神解答，用正负来区分是否overlap，非常精妙！
【在 C****t 的大作中提到】
: sort array [(2,100), (3,-100), (1,200), (2,-200), (4,100), (5,-100)]
: according to keys(point). if two keys are identical, put ( , +) in front
: of (, -). Scan the sorted array, record the sum of values, return the
: maximum... M*log(M)
:
: a
| C****t
发帖数: 53 | 12 What N = 100000000, M=1? I don't think it is related to N.
【在 s****a 的大作中提到】
: naive的做法是插入O(N)查询O(N)
: 如果用线段树或者BIT插入O(logN) 查询O(N) 好像也没啥别的办法了
| v*******C
发帖数: 28 | 13 我想的naive 的做法是按个更新数组中的值，所以是O(sum_i (b_i - a_i +1)), i = 1
...M, 如果区间比较长的话，就比较慢了。
请问大神，这个O(N)是怎么做的？
【在 s****a 的大作中提到】
: naive的做法是插入O(N)查询O(N)
: 如果用线段树或者BIT插入O(logN) 查询O(N) 好像也没啥别的办法了
| s****a
发帖数: 794 | 14 这个不好说的 如果N=10, M=100000000呢。。。
其实还是看实际应用的吧
那就再加一条排序M个操作 就是那个只和M有关的。
具体看哪个好就用什么吧。
另外笔误写错了：
naive的做法是插入O(N)查询*O(1)*
如果用线段树或者BIT插入O(logN) 查询O(N) 好像也没啥别的办法了
【在 C****t 的大作中提到】
: What N = 100000000, M=1? I don't think it is related to N.
| s****a
发帖数: 794 | 15 呃 我说的插入是每次操作 总共m次就成m naive好处就是查询直接出结果就好了。
1
【在 v*******C 的大作中提到】
: 我想的naive 的做法是按个更新数组中的值，所以是O(sum_i (b_i - a_i +1)), i = 1
: ...M, 如果区间比较长的话，就比较慢了。
: 请问大神，这个O(N)是怎么做的？
| C****t
发帖数: 53 | 16 If I was the interviewer, I will not give you N points, just M operations.
N is misleading.
1
【在 v*******C 的大作中提到】
: 我想的naive 的做法是按个更新数组中的值，所以是O(sum_i (b_i - a_i +1)), i = 1
: ...M, 如果区间比较长的话，就比较慢了。
: 请问大神，这个O(N)是怎么做的？
| s****a
发帖数: 794 | 17 这个可没准 没准就是确定的一些资源 在上面刷访问数呢。。。总不能改题目来适合算
法吧。。。
.
【在 C****t 的大作中提到】
: If I was the interviewer, I will not give you N points, just M operations.
: N is misleading.
:
:
: 1
| x***y
发帖数: 633 | 18 It's just merging different intervals so that each new interval after
merging has the same increased value; Then in each interval, find the max
value of that interval in the original array, get the sum of that value and
increased value; compare the sum of each interval, and then return the
largest sum. | l*****n
发帖数: 246 | 19 这个解法不对吧。。。
【在 C****t 的大作中提到】
: sort array [(2,100), (3,-100), (1,200), (2,-200), (4,100), (5,-100)]
: according to keys(point). if two keys are identical, put ( , +) in front
: of (, -). Scan the sorted array, record the sum of values, return the
: maximum... M*log(M)
:
: a
| D*****r
发帖数: 133 | 20 Combine the ideas from Cagnet and shuiya:
For each operation (a, b, k), there are two key/value data to describe the
operation:(a, k) and (b+1, -k), which means all the location starting from
point a will increase the weight by k and all the locations starting from b+
1 will decrease the weight by k. Maintain a BST of all key/value data sorted
by the location (the key of the data). When insert a new key/value data, if
a node with the key exists, update the value of the node by summing up the
new value and the old value in the node.
Finally, traverse the BST in order and sum up the value in the nodes
cumulatively, the cumulative sum at each node is the final weight for that
location.
a
【在 v*******C 的大作中提到】
: 有N个数，初始值为0， 在M个操作之后，找出最大值。 每个操作(a, b, k)表示给第a
: 个到第b个数分别加k。
: 比如说，
: N=5， M= 3, 三组(a,b,k)分别是
: 2, 3, 100;
: 1, 2, 200;
: 4, 5, 100;
: 返回最大值为300.
: 我只能想到很naive的方法，请教版上大神们有没有更好的方法？先谢谢啦！
| U***A
发帖数: 849 | 21 是不是直接用map做？
map的key就是index，value就是到现在为止的增加数木。
int result = INT_MIN;
map mp;
for(int i=0; i
triple x = triples[i];
for(int j=x.first; j<=x.second; j++){
mp[j] += x.third;
result = result > mp[j] ? result:mp[j];
}
}
return result; |
|
