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(M*logM)

Posted by haqishen at 2015-01-03 13:35:05 on Problem 3616
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:
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