Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴Java代码。 O(n*log n) ,带注释import java.util.*; public class Main{ public static void main(String[] args) { Scanner s = new Scanner(System.in); // 创建自定义比较器的PQueue。不会用的自行看手册 // 也可以用数组+二分插入代替。时间复杂度不变。 Comparator<Integer> cmp = new Comparator<Integer>(){ public int compare(Integer a, Integer b){ return b - a; } }; PriorityQueue<Integer> pq = new PriorityQueue<Integer>(1,cmp); // 输入数据 int N = s.nextInt(); stop[] st = new stop[N+1]; for(int i = 0; i < N;i++){ st[i] = new stop(); st[i].dist = s.nextInt(); st[i].f = s.nextInt(); } int L = s.nextInt(), P = s.nextInt(); // 别忘记把终点也算进去 st[N] = new stop(); st[N].dist = L; st[N].f = 0; // 把加油站整理成按离起点的距离升序排序。 for(int i = 0; i < N;i++) st[i].dist = L - st[i].dist; Arrays.sort(st); // 循环所有加油站 // 每个站都检查够不够油 // 不够油的话从之前经过的站里,按从大到小顺序取油。 // 如果取完了还是不够就输出-1 int count = 0, lastpos = 0; for(int i = 0; i <= N;i++){ int d = st[i].dist- lastpos; lastpos = st[i].dist; P -= d; // System.out.println(L+" "+P); while(P < 0 & pq.size() != 0){ P += pq.poll(); count++; } if(P<0){ count = -1; break; } pq.add(st[i].f); } System.out.println(count); } } class stop implements Comparable<stop>{ int dist, f; public int compareTo(stop o) { return this.dist - o.dist; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator