ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1403. Курьер

wa7 please help
Послано Ibragim Atadjanov (Tashkent U of IT) 24 окт 2010 07:47


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