|
|
back to boardSome Help Posted by YoCOmo 14 May 2009 09:06 Hi Im trying to solve this problem, here is my code import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.Hashtable; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.StringTokenizer; import java.util.TreeMap; public class Main{ /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); try { // BufferedReader in = new BufferedReader(new FileReader("stars.in")); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
int numberOfStarts = new Integer(in.readLine());
Map<MyPoint, Integer> xOrderMap = new TreeMap<MyPoint, Integer>(new XComparator()); Map<MyPoint, Integer> yOrderMap = new TreeMap<MyPoint,Integer>(new YComparator()); int starIndex = 0; while(numberOfStarts-->0) { String strStar = in.readLine(); StringTokenizer str = new StringTokenizer(strStar); MyPoint star = new MyPoint(new Integer(str.nextToken()),new Integer(str.nextToken())); xOrderMap.put(star,starIndex); yOrderMap.put(star,starIndex); starIndex++; } Iterator<MyPoint> xIterator = xOrderMap.keySet().iterator(); Iterator<MyPoint> yIterator = yOrderMap.keySet().iterator();
List<MyPoint> xList = new ArrayList<MyPoint>(); List<MyPoint> yList = new ArrayList<MyPoint>();
while(xIterator.hasNext()) { MyPoint xPoint = xIterator.next(); xList.add(xPoint); } while(yIterator.hasNext()) { MyPoint yPoint = yIterator.next(); yList.add(yPoint); } int levels[] = new int[starIndex];
for(int i = 0;i<xList.size();i++) { MyPoint point = xList.get(i); int yIndex = yList.indexOf(point); levels[yIndex<i?yIndex:i]++; } for(int i = 0;i<levels.length;i++) { out.write(levels[i]+""); out.newLine(); } out.flush();
} catch (Exception e) { // TODO Auto-generated catch block e.printStackTrace(); }
} } class XComparator implements Comparator<Object>{ public int compare(Object o1, Object o2) { // TODO Auto-generated method stub MyPoint p1 = (MyPoint)o1; MyPoint p2 = (MyPoint)o2; if(p1.x<p2.x) return -1; if(p1.x>p2.x) return 1;
if(p1.y<p2.y) return -1; if(p1.y>p2.y) return 1;
return 0; }
} class YComparator implements Comparator<Object>{ public int compare(Object o1, Object o2) { // TODO Auto-generated method stub MyPoint p1 = (MyPoint)o1; MyPoint p2 = (MyPoint)o2; if(p1.y<p2.y) return -1; if(p1.y>p2.y) return 1; if(p1.x<p2.x) return -1; if(p1.x>p2.x) return 1; return 0; }
} class MyPoint { int x; int y; public MyPoint(int x, int y) { this.x=x; this.y=y; } public String toString() { return x+","+y; } } The idea is that in xOrderMap and yOrderMap i keep ordered the stars in x or y order. For get the level of a star i just follow the description of the problem all stars to the left and below of a star are of lower level, because of that i look up the index of a star in xOrderMap and yOrderMap and all star that is to the left of a star in both maps are lower than a star. THIS CORRECT? Can someone help me for finding the reason why my code gives WA? Or can somenone help me with some tricky cases? Re: Some Help You don't consider it when a star is below AND to the left. You just count such stars twice. |
|
|