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