POJ2010 贪心优先队列

c头牛,需要选n头（奇数）；学校总共有f的资金， 每头牛分数score和学费cost，问合法招生方案中,中间分数（即排名第(n+1)/2）最高的是多少。 n头牛按照先score后cost从小到大排序； 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心

public class Main { public static void main(String[] args) { new Task().solve(); } } class Task { Queue<Integer> q = new PriorityQueue<Integer>(1, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return (o1 > o2) ? -1 : ((o1 == o2) ? 0 : 1) ; } } ); class Node implements Comparable<Node>{ int score ; int cost ; Node(int score , int cost){ this.score = score ; this.cost = cost ; } @Override public int compareTo(Node o) { if(score != o.score) return score < o.score ? -1 : 1 ; return (cost < o.cost) ? -1 : (cost == o.cost ? 0 : 1) ; } @Override public String toString() { return "Node [score=" + score + ", cost=" + cost + "]"; } } void solve() { int n = in.nextInt() ; int c = in.nextInt() ; int f = in.nextInt() ; Node[] node = new Node[c+1] ; int[] minCostLeft = new int[c+1] ; int[] minCostRight = new int[c+1] ; for(int i = 1 ; i <= c ; i++){ node[i] = new Node(in.nextInt() , in.nextInt()) ; } Arrays.sort(node , 1 , 1+c) ; int half = n/2 , sumCost = 0 ; int begin = half+1 , end = c - half ; q.clear() ; for(int i = 1 ; i <= c ; i++){ if(q.size() > half) sumCost -= q.poll() ; if(i >= begin) minCostLeft[i] = sumCost ; sumCost += node[i].cost ; q.add(node[i].cost) ; } q.clear() ; sumCost = 0 ; for(int i = c ; i >= 1 ; i--){ if(q.size() > half) sumCost -= q.poll() ; if(i <= end) minCostRight[i] = sumCost ; sumCost += node[i].cost ; q.add(node[i].cost) ; } int res = -1 ; for(int i = end ; i >= begin ; i--){ if(node[i].cost + minCostLeft[i] + minCostRight[i] <= f){ res = node[i].score ; break ; } } out.print(res) ; out.flush() ; } InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); } class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = new StringTokenizer(""); } private void eat(String s) { tokenizer = new StringTokenizer(s); } public String nextLine() { try { return reader.readLine(); } catch (Exception e) { return null; } } public boolean hasNext() { while (!tokenizer.hasMoreTokens()) { String s = nextLine(); if (s == null) return false; eat(s); } return true; } public String next() { hasNext(); return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } public BigInteger nextBigInteger() { return new BigInteger(next()); } }