| ||||||||||
| 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