Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴Java代码。 O(n*log n) ,带注释

Posted by haqishen at 2015-01-05 18:05:23 on Problem 2431
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator