| ||||||||||
| 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代码。排序后贪心算法。//可以用二分插入继续优化。
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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator