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); }
Leave A Comment