|
|
вернуться в форумwa5. help I got wa5. I cant find my bug. please help to find my bug or give me the test my prog fail import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.ArrayList; import java.util.Collections; import java.util.Locale; public class Timus1105 {
private static StreamTokenizer st; private static double l; private static int n; private static ArrayList<Interval> list; public static void main(String[] args) { Locale.setDefault(Locale.US); st = new StreamTokenizer(new InputStreamReader(System.in)); l = - nextDouble() + nextDouble(); n = nextInt(); list = new ArrayList<Interval>();
for (int i = 0; i < n; i++) { list.add(new Interval(nextDouble() , nextDouble(), i + 1));
} Collections.sort(list); for (int i = 1; i < list.size() ; ) { if(list.get(i).r <= list.get(i - 1).r){ list.remove(i); } else{ if(i < list.size() - 1 && list.get(i).r < list.get(i + 1).r && list.get(i + 1).l <= list.get(i - 1).r){ list.remove(i); } else i++; } } double sum1 = 0; double sum2 = 0; for (int i = 0; i < list.size(); i++) { if(i % 2 == 0){ sum1 += list.get(i).r - list.get(i).l; } else{ sum2 += list.get(i).r - list.get(i).l; } }
for (int i = 0; i < list.size() - 1; i++) { double r = Math.min(list.get(i).r, list.get(i + 1).l); double l = Math.max(list.get(i + 1).l, list.get(i).r); list.get(i).r = r; list.get(i + 1).l = l; }
double sum = 0; ArrayList<Integer> ans = new ArrayList<Integer>(); for (int i = 0; i < list.size(); i++) { double x = list.get(i).r - list.get(i).l; if(x > 0){ sum += x; ans.add(list.get(i).i); } }
if(sum1 > sum ){ sum = sum1; ans.clear(); for (int i = 0; i < list.size(); i+=2) { ans.add(list.get(i).i); } } if(sum1 > sum){ sum = sum2; ans.clear(); for (int i = 1; i < list.size(); i+=2) { ans.add(list.get(i).i); } } if(3 * sum >= 2 * l){ System.out.println(ans.size()); for (int i = 0; i < ans.size(); i++) { System.out.println(ans.get(i)); } } else{ System.out.println(list.size()); for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); } } }
static double nextDouble(){ try { st.nextToken(); } catch (IOException e) { e.printStackTrace(); } return st.nval; }
static int nextInt(){ try { st.nextToken(); } catch (IOException e) { e.printStackTrace(); } return (int) st.nval; }
static class Interval implements Comparable<Interval>{ double l, r; int i;
Interval(double l1, double r1, int i1){ l = l1; r = r1; i = i1; } @Override public int compareTo(Interval o) { int ret = (int) (this.l - o.l); if(ret == 0){ ret = (int) (o.r - this.r); } return ret; }
} } |
|
|