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 – A[i].first) < d. 如果不满足, 要往前移动j,并且把A[j]从cur中踢除.. 然后每次取最大值.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int d = in.readInt();
        Pair<Integer, Integer>[] ary = new Pair[n];
        for (int i = 0; i < n; i++) {
            ary[i] = Pair.makePair(in.readInt(),in.readInt());
        }
        Arrays.sort(ary);
        long cur = 0;
        int j = 0;
        long max = 0;
        for (int i = 0; i < ary.length; i++) {
            cur += ary[i].second;
            while (j < i && Math.abs(ary[i].first - ary[j].first)>=d){
                cur -= ary[j].second;
                j++;
            }
            max = Math.max(max, cur);
        }
        out.print(max);
    }