POJ2010 贪心优先队列

本文主要是介绍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>() {@Overridepublic 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 ;}@Overridepublic int compareTo(Node o) {if(score != o.score)return score < o.score ? -1 : 1 ;return (cost < o.cost) ? -1 : (cost == o.cost ? 0 : 1) ;}@Overridepublic 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());}}

这篇关于POJ2010 贪心优先队列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---