|
|
back to boardwa7 please help import java.util.Arrays; import java.util.Scanner; public class Timus1403 { /** * @param args */ public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); Order[] order = new Order[n]; int[] num = new int[100001]; int[] ans = new int[100001]; boolean[] used = new boolean[100001]; Arrays.fill(used, false); for (int i = 0; i < order.length; i++) { int d = input.nextInt(); int p = input.nextInt(); order[i] = new Order(i + 1, d, p); } for (int i = 0; i < num.length; i++) { num[i] = i; } Arrays.sort(order); int count = 0; for (int i = 0; i < order.length; i++) { int j = order[i].deadline; if(num[j] > 0 && !used[num[j]]){ count++; int x = num[j]; ans[num[j]] = order[i].index; used[num[j]] = true; num[num[j]] = num[j] - 1; if(x == j){ continue; } num[order[i].deadline]--;
} } System.out.println(count); for (int i = 0; i < used.length; i++) { if(used[i]){ System.out.print(ans[i] + " "); } }
} } class Order implements Comparable<Order>{ public int index; public int deadline; public int price;
public Order(int i, int d, int p){ index = i; deadline = d; price = p; }
@Override public String toString(){ String ret = ""; ret+= this.index + " " + this.deadline + " " + this.price; return ret; }
public int compareTo(Order other) { return -(this.price - other.price); }
} Edited by author 24.10.2010 08:20 |
|
|