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代码。排序后贪心算法。

Posted by haqishen at 2015-01-04 13:02:28 on Problem 1065
//可以用二分插入继续优化。
import java.util.*;

public class Main{
	
	public static void main(String args[]){
		Scanner s = new Scanner(System.in);
		LinkedList<stick> ll = new LinkedList<stick>();
		int T = s.nextInt();
		
		for(int t = 0; t < T; t++){
			int n = s.nextInt();
			stick sts[] = new stick[n];
			ll.clear();
			
			for(int i = 0; i < n; i++){
				sts[i] = new stick();
				sts[i].l = s.nextInt();
				sts[i].w = s.nextInt();
			}
			Arrays.sort(sts);
			ll.add(sts[0]);						
			int ans = 1;
			
			for(int i = 1; i < n; i++){				
				int index = 0;
				for(stick st : ll){
					if(sts[i].l >= st.l & sts[i].w >= st.w)
						break;
					index++;
				}
				
				if(index >= ll.size()){
					ans ++;					
				}else{
					ll.remove(index);
				}
				ll.add(index, sts[i]);
			}
			System.out.println(ans);
		}
	}
	
}

class stick implements Comparable<stick>{
	int l,w;
	public int compareTo(stick o) {
		if(this.l == o.l)
			return this.w - o.w;
		else
			return this.l - o.l;		
	}	
}

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