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