Codeforces Round #312 (Div. 2) A. Lala Land and Apple Trees

原题:http://codeforces.com/problemset/problem/558/A

---

题目大意: 坐标轴上, 每个坐标上有一颗苹果树, 坐标的值代表的值是苹果的数量, 人从0开始走, 可以往左,也可以往右, 当遇到一个苹果树时, 人必须往反向走, 问:最多拿多少个的苹果?

---

分析: 无非开始往左or往右, 两种情况, 当遇到另一边没有树的时候, 停止, 所以最多拿max([left+1,right],[right+1,left]).left,right 原点左右的树的数量. 建个Pair<Integer,Integer>, 前边是index, 后边是value, 然后sort下 加一下就出来了.

  public void solve(int testNumber, Scanner in, PrintWriter out) {
        int n = in.nextInt();
        ArrayList<Pair<Integer,Integer>> pos = new ArrayList<Pair<Integer,Integer>>();
        ArrayList<Pair<Integer,Integer>> neg = new ArrayList<Pair<Integer, Integer>>();
        for (int i = 0; i < n; i++) {
            int cor = in.nextInt();
            if (cor > 0)
                pos.add(Pair.makePair(cor,in.nextInt()));
            else
                neg.add(Pair.makePair(cor,in.nextInt()));
        }
        Collections.sort(pos);
        Collections.sort(neg);
        int res = 0;
        for (int i = 0; i < Math.min(pos.size(), neg.size()+1); i++) {
            res += pos.get(i).second;
        }
        for (int i = 0; i < Math.min(neg.size(), pos.size()+1); i++) {
            res += neg.get(i).second;
        }
        out.println(res);
    }