Codeforces Round #321 (Div. 2) B. Kefa and Company | 书脊
Codeforces Round #321 (Div. 2) B. Kefa and Company
原题:http://codeforces.com/contest/580/problem/B
题目大意: 给n,d两个整数,给n个pair<first,second>, 让你找second的合最大的pair组, 满足first之间的差值不大于d. 返回sum.
分析: 因为要满足的条件是pair中, first的差值不大于d, 所以首先我们要以first为基准, 排序n个pair. 其次,我们要找期中second的合最大的数组, 满足first的差不大于d, 这时, 我们已经知道, 答案在已排序的数组中, 并且是连续的子数组. 这时, 我们用双指针扫描. 第一个指针i扫整个pair组的每一个pair, 第二个指针j在i后边, 用来判断当前元素是否能满足abs(A[cur] .first �C A[i].first) < d. 如果不满足, 要往前移动j,并且把A[j]从cur中踢除.. 然后每次取最大值.
Read full article from Codeforces Round #321 (Div. 2) B. Kefa and Company | 书脊
No comments:
Post a Comment