logo
Redian新闻
>未名空间
>Fashion - 美丽时尚
>
购买朱莉的GC
avatar
购买朱莉的GC# Fashion - 美丽时尚
v*C
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的方法，请教版上大神们有没有更好的方法？先谢谢啦！
avatar
X*D
2 楼
上次朱莉搞DEAL，赠送了25刀的购物卡，有姐妹们想卖的吗，我有意购买。
avatar
n*s
3 楼
直觉就是每次把index a->b的加K， 最后再选个最大数就可以了。
avatar
m*u
4 楼
据说所谓的GC是大家都一样的code 如果不是的话 可以跟我联系哈~ 要买50块以上才
能用的哦
avatar
C*t
5 楼
有点像最少会议室问题…不过现在不是按照起点时间排序，是所有的端点排序，左端点
正值，右端点正的相反数。从左到右，记录和的最大值…
avatar
X*D
6 楼
OK,我记住了，到时候联系你～！

【在 m********u 的大作中提到】
: 据说所谓的GC是大家都一样的code 如果不是的话 可以跟我联系哈~ 要买50块以上才
: 能用的哦
avatar
v*C
7 楼
不好意思，刚没说清楚，K是大于0的不定的数。

【在 n*******s 的大作中提到】
: 直觉就是每次把index a->b的加K， 最后再选个最大数就可以了。
avatar
s*y
8 楼
要是不是也跟我联系吧
avatar
v*C
9 楼
大神，能展开说说吗？不是很理解。。。

【在 C****t 的大作中提到】
: 有点像最少会议室问题…不过现在不是按照起点时间排序，是所有的端点排序，左端点
: 正值，右端点正的相反数。从左到右，记录和的最大值…
avatar
X*D
10 楼
好的，记住了。：）

【在 s******y 的大作中提到】
: 要是不是也跟我联系吧
avatar
n*s
11 楼
改了， 呵呵， 其实就是问你怎么找最大数吧？
或许需要改进一下， 只需要搜索最小的a和最大的b之间就可以了， 还需要改善的话，
就已经不是年老色衰的人能想明白的了。

【在 v*******C 的大作中提到】
: 不好意思，刚没说清楚，K是大于0的不定的数。
avatar
X*D
12 楼
GC是不是还没到吧，等到了我看看是如何的抵扣方式阿。
avatar
n*s
13 楼
好像是说把[a, b]排序， 纪录当前最大值， 然后向右滑， 最后返回最大值。

【在 v*******C 的大作中提到】
: 大神，能展开说说吗？不是很理解。。。
avatar
C*t
14 楼
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的方法，请教版上大神们有没有更好的方法？先谢谢啦！
avatar
s*a
15 楼
你的这个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
avatar
s*a
16 楼
naive的做法是插入O(N)查询O(N)
如果用线段树或者BIT插入O(logN) 查询O(N) 好像也没啥别的办法了
avatar
v*C
17 楼
多谢大神解答，用正负来区分是否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
avatar
C*t
18 楼
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) 好像也没啥别的办法了
avatar
v*C
19 楼
我想的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) 好像也没啥别的办法了
avatar
s*a
20 楼
这个不好说的 如果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.
avatar
s*a
21 楼
呃 我说的插入是每次操作 总共m次就成m naive好处就是查询直接出结果就好了。

1

【在 v*******C 的大作中提到】
: 我想的naive 的做法是按个更新数组中的值，所以是O(sum_i (b_i - a_i +1)), i = 1
: ...M, 如果区间比较长的话，就比较慢了。
: 请问大神，这个O(N)是怎么做的？
avatar
C*t
22 楼
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)是怎么做的？
avatar
s*a
23 楼
这个可没准 没准就是确定的一些资源 在上面刷访问数呢。。。总不能改题目来适合算
法吧。。。

.

【在 C****t 的大作中提到】
: If I was the interviewer, I will not give you N points, just M operations.
: N is misleading.
:
:
: 1
avatar
x*y
24 楼
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.
avatar
l*n
25 楼
这个解法不对吧。。。

【在 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
avatar
D*r
26 楼
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的方法，请教版上大神们有没有更好的方法？先谢谢啦！
avatar
U*A
27 楼
是不是直接用map做？
map的key就是index，value就是到现在为止的增加数木。
int result = INT_MIN;
map mp;
for(int i=0; itriple 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;
相关阅读
感謝花生版This dress Ok for Company's Holiday Party??the body shop 30 for 3 又回来了，可惜网站出问题了奔~~~~~~~~~~附加俺今儿做的饭~~~~今天的收获<讨论>JMS什么肤色的适合什么颜色的衣服Theory men's cashmere sweater $91 + tax奔个最新的搭配GUCCI毯子$74.96JMS说说,168公分高,回国可以带那种手包过关么？孕妇服装 by Ann Taylor (转载)BG 100减25的codehappy holiday~闪sephora 的同一个code不能用两次了求推荐单价300刀上下的鞋子，包包和衣服品牌？奖励包子，哪里买Polo Ralph Lauren便宜?[DEAL]the body shop Cyber Monday 3 for $30+FSNM, Saks Designer handbags and apparel on sale 12/140岁的女人，那个牌子比较合适？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。