e-olymp 1228. Добавить все

27/12/2018 by Саша Рябова

Условие

Условие задачи отражает Вашу задачу: необходимо просто сложить числа. Но это будет унизительно если Вас попросят просто написать такую программу на языке C/C++ для заданного множества чисел. Давайте внесем в задачу оттенок изобретательности.

Введем понятие стоимости для операции сложения. Стоимость сложения двух чисел положим равным их сумме. Например, сложить числа $1$ и $10$ стоит $11$. Стоимость сложения $1,2$ равна $3$. Складывать числа можно разными способами:

$1 + 2 = 3$ (стоимость = 3), $3 + 3 = 6$ (стоимость = 6), Всего = 9
$1 + 3 = 4$ (стоимость = 4), $2 + 4 = 6$ (стоимость = 6), Всего = 10
$2 + 3 = 5$ (стоимость = 5), $1 + 5 = 6$ (стоимость = 6), Всего = 11

Надеемся, Вы поняли Вашу задачу. Вам необходимо сложить все числа так, чтобы суммарная стоимость их сложения была наименьшая.

Входные данные

Начинаются целым числом $n (2 \leq n \leq 100000)$, за которым следуют $n$ целых неотрицательных чисел (все числа меньше $100000$).

Выходные данные

Вывести наименьшую стоимость сложения всех чисел.

Тесты

Входные данные	Выходные данные
$4$ $10$ $12$ $13$ $11$	$92$
$5$ $100$ $11$ $8$ $30$ $12$	$272$
$4$ $2$ $2$ $2$ $2$	$16$
$6$ $1$ $2$ $3$ $4$ $5$ $6$	$51$

Код решения

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        PriorityQueue<Long> nums = new PriorityQueue<Long>();
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        for (int i = 0; i < n; i++) {
            long number = sc.nextLong();
            nums.add(number);
        }

        long minSum = 0;
        long a;
        long b;
        while (!nums.isEmpty()) {
            
            a = nums.poll();
                     
            if (nums.isEmpty()) {
                break;
            }
            b = nums.poll();
            minSum += a + b;            
            nums.add(a + b);

        }
        System.out.println(minSum);

    }
}

import java.util.PriorityQueue;

import java.util.Scanner;

public class Main{

public static void main(String[] args) {

PriorityQueue<Long> nums = new PriorityQueue<Long>();

Scanner sc = new Scanner(System.in);

long n = sc.nextLong();

for (int i = 0; i < n; i++) {

long number = sc.nextLong();

nums.add(number);

}

long minSum = 0;

long a;

long b;

while (!nums.isEmpty()) {

a = nums.poll();

if (nums.isEmpty()) {

break;

}

b = nums.poll();

minSum += a + b;

nums.add(a + b);

}

System.out.println(minSum);

}

Решение

Стоимость сложения всех чисел будет минимальной, если на каждом следующем шаге мы будем складывать два наименьшие числа из множества $A$, состоящего из данного ряда чисел и уже вычисленных «частичных сумм». Таким образом, каждый шаг цикла поиска минимальной стоимости сложения будет состоять из нахождения двух минимальных чисел из множества, удаления этих чисел из множества $A$ и добавления в него результата их суммирования. В специальную переменную $minSum$ будем также каждый раз добавлять результат этого суммирования. Таким образом, количество элементов во множестве будет с каждым шагом уменьшаться на одно, и в конце, когда в нем останется единственный элемент, переменная $minSum$ будет содержать искомую стоимость сложения всех чисел.
Реализовать такой код достаточно просто, если реализовать множество $A$ в виде очереди с приоритетом.

Ссылки

Условие задачи на e-olymp.com
Код решения на ideone.com

e-olymp 93. Truck driving

27/12/2018 by Саша Рябова

Task

Umidsh Izadish is a truck driver and wants to drive from a city to another city while there exists a dedicated straight road between each pair of cities in that country. Amount of consumed fuel is the distance between two cities which is computed from their coordinates. There is a gas station in each city, so Umidsh can refuel the gas container of his truck. Your job is to compute the minimum necessary volume of gas container of Umidsh’s Truck.

Input data

The first line of input contains an integer, the number of test cases. Following, there are data for test cases. Each test case begins with a line containing one integer $C$, $2 /leq C /leq 200$, which is the number of cities. The next $C$ lines each contain two integers $x$,$y$ representing the coordinate of one city. First city is the source city and second is the destination city of Umidsh.

Output data

There should be one line for each test case in output. Each line should contain one floating point number which is the minimum necessary volume of truck’s gas container, printed to three decimals.

Tests

Input	Output
$2$ $2$ $0$ $0$ $3$ $4$ $3$ $17$ $4$ $19$ $4$ $18$ $5$	$5.000$ $1.414$
$1$ $3$ $4$ $5$ $4$ $6$ $4$ $7$	$1.000$
$2$ $4$ $0$ $1$ $0$ $-1$ $1$ $0$ $-1$ $0$ $3$ $8$ $9$ $0$ $1$ $14$ $14$	$1.414$ $11.314$

Code

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class TruckDriving {

    public class Node implements Comparable<Node> {

        Integer first;
        Integer second;

        @Override
        public int compareTo(Node other) {
            if (this.first != other.first) {
                return this.first.compareTo(other.first);
            } else {
                return this.second.compareTo(other.second);
            }
        }
    }

    int distance[] = new int[200];

    public TruckDriving() {

        Scanner sc = new Scanner(System.in);
        int testCaseCount = sc.nextInt();
        for (int i = 0; i < testCaseCount; i++) {
            int cityCount = sc.nextInt();
            ArrayList<Node> coordCity = new ArrayList<Node>(cityCount);
            for (int j = 0; j < cityCount; j++) {
                int coordX = sc.nextInt();
                int coordY = sc.nextInt();
                Node city = new Node();
                city.first = coordX;
                city.second = coordY;
                coordCity.add(city);
            }

            findMinimum(coordCity, cityCount);
            // System.out.println(distance.get(1));
            double res = Math.sqrt(distance[1]);
            System.out.format("%.3f", res);
            System.out.println();
        }

    }

    public void findMinimum(ArrayList<Node> coordCity, int cityCount) {
        //  System.out.println(distance);
        distance[0] = 0;
        for (int i = 1; i < cityCount; i++) {
            distance[i] = Integer.MAX_VALUE;
        }

        PriorityQueue<Node> q = new PriorityQueue<Node>();
        Node zeroPair = new Node();
        zeroPair.first = 0;
        zeroPair.second = 0;

        q.add(zeroPair);
        while (!q.isEmpty()) {
            int num_v = q.peek().second;
            Node cur = coordCity.get(num_v);
            int distv = -q.peek().first;
            q.poll();
            for (int j = 0; j < cityCount; j++) {
                int distan = Math.max(distv, (cur.first - coordCity.get(j).first) * (cur.first - coordCity.get(j).first) + (cur.second - coordCity.get(j).second) * (cur.second - coordCity.get(j).second));
                if (distance[j] > distan) {
                    distance[j] = distan;
                    Node tempPair = new Node();
                    tempPair.first=-distan;
                    tempPair.second=j;
                    q.add(tempPair);
                }
            }

        }
    }

    public static void main(String[] args) {
        TruckDriving tr = new TruckDriving();

    }
}

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.PriorityQueue;

import java.util.Scanner;

public class TruckDriving {

public class Node implements Comparable<Node> {

Integer first;

Integer second;

@Override

public int compareTo(Node other) {

if (this.first != other.first) {

return this.first.compareTo(other.first);

} else {

return this.second.compareTo(other.second);

}

int distance[] = new int[200];

public TruckDriving() {

Scanner sc = new Scanner(System.in);

int testCaseCount = sc.nextInt();

for (int i = 0; i < testCaseCount; i++) {

int cityCount = sc.nextInt();

ArrayList<Node> coordCity = new ArrayList<Node>(cityCount);

for (int j = 0; j < cityCount; j++) {

int coordX = sc.nextInt();

int coordY = sc.nextInt();

Node city = new Node();

city.first = coordX;

city.second = coordY;

coordCity.add(city);

}

findMinimum(coordCity, cityCount);

// System.out.println(distance.get(1));

double res = Math.sqrt(distance[1]);

System.out.format("%.3f", res);

System.out.println();

}

public void findMinimum(ArrayList<Node> coordCity, int cityCount) {

// System.out.println(distance);

distance[0] = 0;

for (int i = 1; i < cityCount; i++) {

distance[i] = Integer.MAX_VALUE;

}

PriorityQueue<Node> q = new PriorityQueue<Node>();

Node zeroPair = new Node();

zeroPair.first = 0;

zeroPair.second = 0;

q.add(zeroPair);

while (!q.isEmpty()) {

int num_v = q.peek().second;

Node cur = coordCity.get(num_v);

int distv = -q.peek().first;

q.poll();

for (int j = 0; j < cityCount; j++) {

int distan = Math.max(distv, (cur.first - coordCity.get(j).first) * (cur.first - coordCity.get(j).first) + (cur.second - coordCity.get(j).second) * (cur.second - coordCity.get(j).second));

if (distance[j] > distan) {

distance[j] = distan;

Node tempPair = new Node();

tempPair.first=-distan;

tempPair.second=j;

q.add(tempPair);

}

public static void main(String[] args) {

TruckDriving tr = new TruckDriving();

}

Solution

We can interpretate the set of the cities as weighted graph, which vertices represent cities and weight of each edge between two vertices is the gas volume required for passing the distance between corresponding cities.
The volume of truck’s gas container depends on the gas volume required for arrival to the each next station of the Umidsh’s way. The maximum between gas volume required to get to the city $A$ and gas volume required to pass the way from the city $a$ to the city $B$ represents the minimum necessary gas volume required to get to the city $B$ through the city $A$. So the volume of truck’s gas container would turn to minimum, when the maximum gas volume required for passing the distance between each two stations of his way would turn to minimum. Thus we could use modified Dijkstra’s algorithm to find the biggest value among the weights of an edges between each two stations of the way between vertice 0 and vertice 1.

Note: To use Node objects in the PriorityQueue, there should be a way to compare this objects. Thus, it was required to overwrite a method CompareTo so that we could implement interface Comparable

References

The task at e-olymp.com

e-olymp 161. Роботы

06/11/2018 by Костя Григорян

Задача

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $A$, а вторую – роботы типа $B$. Чтобы сэкономить на покупке роботов, было решено купить не новых роботов последней модели, а уже бывших в употреблении. В результате, время, которое разные роботы тратили на выполнение одной и той же операции, существенно различалось, что привело к трудностям в планировании работ.

Составьте программу, которая по заданному набору роботов обоих типов определяет, за какое минимальное время они смогут обработать определенное количество деталей.

Входные данные

В первой строке натуральное число $N$, $1 ≤ N ≤ 100000$ – количество деталей, которое необходимо обработать.

Во второй строке натуральное число $N_a$, $1 ≤ N_a ≤ 1000$ – количество роботов, выполняющих первую операцию.

В третьей строке через пробел $N_a$ натуральных чисел $A_{i}$, $1 ≤ A_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $A$ на выполнение операции.

В четвертой строке натуральное число $N_b$, $1 ≤ N_b ≤ 1000$ – количество роботов, выполняющих вторую операцию.

В пятой строке через пробел $N_b$ натуральных чисел $B_{i}$, $1 ≤ B_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $B$ на выполнение операции.

Выходные данные

В первой строке одно целое число – минимальное время, за которое все $N$ деталей будут обработаны сначала роботом типа $A$, а потом роботом типа $B$. Временем передачи детали от робота типа $A$ роботу типа $B$ пренебречь.

Тесты

Входные данные	Выходные данные
[latex]6[/latex]	[latex]9[/latex]
[latex]3[/latex]
[latex]1\, 3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]2[/latex]	[latex]5[/latex]
[latex]2[/latex]
[latex]3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]5[/latex]	[latex]41[/latex]
[latex]4[/latex]
[latex]84\, 50\, 50\ 8[/latex]
[latex]2[/latex]
[latex]1\, 21[/latex]
[latex]100[/latex]	[latex]100[/latex]
[latex]2[/latex]
[latex]1\, 50[/latex]
[latex]4[/latex]
[latex]1\, 2\, 3\, 4[/latex]

Код программы

import java.util.*;

public class Main {
	
	private static class Pair{
		int a, b;
		
		public Pair(int a, int b) {
			this.a=a;
			this.b=b;
		}
		
	}
	
	public static void main (String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int na = scanner.nextInt();
		int[] A = new int[na];
		int[] times = new int[n];
		PriorityQueue<Pair> q = new PriorityQueue<>((a, b)->a.a-b.a);
		for(int i=0; i<na; i++) {
			A[i] = scanner.nextInt();
			q.add(new Pair(A[i], A[i]));
		}
		for(int i=0; i<n; i++) {
			Pair pair=q.poll();
			times[i]=pair.a;
			q.add(new Pair(pair.a+pair.b, pair.b));
		}
		q.clear();
		int nb = scanner.nextInt();
		int[] B = new int[nb];
		int max_time=0;
		for(int i=0; i<nb; i++) {
			B[i] = scanner.nextInt();
			q.add(new Pair(B[i], B[i]));
		}
		for(int i=n-1; i>=0; i--) {
			Pair pair=q.poll();
		    times[i]+=pair.a;
			q.add(new Pair(pair.a+pair.b, pair.b));
			if(times[i]>max_time)
				max_time=times[i];
		}
		System.out.println(max_time);
	}
}

import java.util.*;

public class Main {

private static class Pair{

int a, b;

public Pair(int a, int b) {

this.a=a;

this.b=b;

}

public static void main (String[] args) {

Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt();

int na = scanner.nextInt();

int[] A = new int[na];

int[] times = new int[n];

PriorityQueue<Pair> q = new PriorityQueue<>((a, b)->a.a-b.a);

for(int i=0; i<na; i++) {

A[i] = scanner.nextInt();

q.add(new Pair(A[i], A[i]));

}

for(int i=0; i<n; i++) {

Pair pair=q.poll();

times[i]=pair.a;

q.add(new Pair(pair.a+pair.b, pair.b));

}

q.clear();

int nb = scanner.nextInt();

int[] B = new int[nb];

int max_time=0;

for(int i=0; i<nb; i++) {

B[i] = scanner.nextInt();

q.add(new Pair(B[i], B[i]));

}

for(int i=n-1; i>=0; i--) {

Pair pair=q.poll();

times[i]+=pair.a;

q.add(new Pair(pair.a+pair.b, pair.b));

if(times[i]>max_time)

max_time=times[i];

}

System.out.println(max_time);

}

Решение задачи

Решение состоит из двух этапов.
Найдем минимальное время, которое понадобится роботам первого типа, чтобы завершить обработку всех деталей. Для каждой детали, мы берем робота с минимальным временем завершения обработки этой детали и обновляем его время на время обработки им одной детали.
На втором этапе фактически делаем тоже, что и на первом с учетом следующей стратегии комбинации. Для детали, которая пройдет первый этап последней, на втором этапе резервируем самый быстрый из роботов второго типа.
Теперь оценим сложность работы алгоритма. Для каждой из $n$ деталей работает логарифмическая вставка в очередь с приоритетом. Получаем, что асимптотическая вычислительная сложность алгоритма $O(n\, \log n)$.

Ссылки

Условие задачи на e-olymp
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова:

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: PriorityQueue

e-olymp 1228. Добавить все

Условие

Входные данные

Выходные данные

Тесты

Код решения

Решение

Ссылки

e-olymp 93. Truck driving

Task

Input data

Output data

Tests

Code

Solution

References

e-olymp 161. Роботы

Задача

Входные данные

Выходные данные

Тесты

Код программы

Решение задачи

Ссылки