| ||||||||||
| 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(M*logM)
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = s.nextInt(), M = s.nextInt(), R = s.nextInt();
interval it[] = new interval[M];
for(int i = 0; i < M; i++){
it[i] = new interval();
it[i].sh = s.nextInt();
it[i].eh = s.nextInt() + R-1;
it[i].ce = s.nextInt();
}
Arrays.sort(it);
long max = 0;
for(int i = 0; i < M; i++){
int l = 0, index = i-1;
while(index >= l){
int temp = (index + l) / 2;
if(it[temp].eh < it[i].sh){
l = temp + 1;
}else if(it[temp].eh >= it[i].sh){
index = temp - 1;
}
}
if(index < 0){
it[i].max = Math.max(max, it[i].ce);
}else{
it[i].max = Math.max(max, it[index].max + it[i].ce);
}
max = it[i].max;
}
System.out.println(max);
}
}
class interval implements Comparable<interval>{
int sh, eh, ce;
long max;
public int compareTo(interval o) {
return this.eh - o.eh;
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator