Условие задачи

Массив сортируется методом выбора по возрастанию. Сколько раз меняет свое место первый по порядку элемент?

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

Первая строка содержит количество элементов в массиве $n$ $\left(1\leqslant n\leqslant1000\right)$. Во второй строке задан сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10^9$.

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

Вывести количество перемещений первого элемента.

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		java.util.Scanner in = new java.util.Scanner(System.in);
		int n = in.nextInt();
		int []x = new int [n];
	    int counter = 0; // количество перемещений
	    for (int i = 0; i < n; i++){
	        x[i] = in.nextInt();
	    }
	    int first = x[0]; // первый по порядку элемент
	    for (int i = 0; i < n - 1; i++) {
	        int min = i; // индекс минимального элемента
	        for (int j = i + 1; j < n; j++) {
	            if (x[j] < x[min]) min = j;
	        }
	        if((x[i] == first || x[min] == first) && x[i] != x[min]) counter ++;
	        int t = x[i];
		    x[i] = x[min];
		    x[min] = t;
	    }
    	System.out.print(counter);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

java.util.Scanner in = new java.util.Scanner(System.in);

int n = in.nextInt();

int []x = new int [n];

int counter = 0; // количество перемещений

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

x[i] = in.nextInt();

}

int first = x[0]; // первый по порядку элемент

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

int min = i; // индекс минимального элемента

for (int j = i + 1; j < n; j++) {

if (x[j] < x[min]) min = j;

}

if((x[i] == first || x[min] == first) && x[i] != x[min]) counter ++;

int t = x[i];

x[i] = x[min];

x[min] = t;

}

System.out.print(counter);

}

Решение

Применяем метод выбора по возрастанию. Для этого мы ищем наименьший элемент в массиве и перемещаем его на первое место. Затем ищем второй наименьший элемент и перемещаем его уже на второе место после первого наименьшего элемента. Этот процесс продолжается до тех пор, пока в массиве не закончатся неотсортированные элементы. Для того, чтобы найти количество перемещений первого элемента, мы проверяем совпадает ли значение первого элемента со значениями перемещаемых элементов. Также смотрим, чтобы значения этих элементов не были равны между собой, так как в этом случае сам элемент никуда не сдвигается.

Подробное изложение алгоритма сортировки можно найти в этой статье .

Задача

Черный Ящик представляет собой примитивную базу даных. Он может хранить массив целых чисел, а также имеет специальную переменную $i$. В начальный момент Черный Ящик пустой, переменная $i$ равна $0$. Черный Ящик обрабатывает последовательность команд (транзакций). Существует два типа транзакций:
ADD(x): добавить элемент x в Черный Ящик;
GET: увеличить $i$ на $1$ и вывести $i$-ый минимальный элемент среди всех чисел, находящихся в Черном Ящике.
Помните, что $i$-ый минимальный элемент находится на $i$-ом месте после того как все элементы Черного Ящика будут отсортированы в неубывающем порядке.
Рассмотрим работу черного ящика на примере:

№	Транзакция	$i$	Содержимое Черного Ящика после транзакции	Ответ
1	ADD(3)	0	3
2	GET	1	3	3
3	ADD(1)	1	1, 3
4	GET	2	1, 3	3
5	ADD(-4)	2	-4, 1, 3
6	ADD(2)	2	-4, 1, 2, 3
7	ADD(8)	2	-4, 1, 2, 3, 8
8	ADD(-1000)	2	-1000, -4, 1, 2, 3, 8
9	GET	3	-1000, -4, 1, 2, 3, 8	1
10	GET	4	-1000, -4, 1, 2, 3, 8	2
11	ADD(2)	4	-1000, -4, 1, 2, 2, 3, 8

Необходимо разработать эффективный алгоритм выполнения заданной последовательности транзакций. Максимальное количество транзакций ADD и GET равно $30000$ (каждого типа).
Опишем последовательность транзакций двумя целочисленными массивами:

$A_1, \ A_2, \ldots , \ A_m:$ последовательность элементов, которая будет добавляться в Черный Ящик. Элементами являются целые числа, по модулю не большие $2 000 000 000$, $m \leq 30000$. Для выше описанного примера $A = \left (3, 1, -4, 2, 8, -1000, 2 \right).$
$u_1, \ u_2, \ldots, \ u_n:$ последовательность указывает на количество элементов в Черном Ящике в момент выполнения первой, второй, … $n$-ой транзакции GET. Для выше описанного примера $u = \left (1, 2, 6, 6 \right ).$

Работа Черного Ящика предполагает, что числа в последовательности $u_1, \ u_2, \ldots , \ u_n$ отсортированы в неубывающем порядке, $n \leq m$, а для каждого $p \left (1 \leq p \leq n \right )$ имеет место неравенство $p \leq u(p) \leq m$. Это следует из того, что для $p$-го элемента последовательности $u$ мы выполняем GET транзакцию, которая выводит $p$-ый минимальный элемент из набора чисел $A_1, \ A_2, \ldots , \ A_{u_p}$.

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

Состоит из следующего набора чисел: $m, \ n, \ A_1, \ A_2, \ldots , \ A_m, \ u_1, \ u_2, \ldots , \ u_n.$ Все числа разделены пробелами и (или) символом перевода на новую строку.

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

Вывести ответы Черного Ящика на последовательность выполненных транзакций. Каждое число должно выводиться в отдельной строке.

Тесты

Входные данные	Выходные данные
7 4 3 1 -4 2 8 -1000 2 1 2 6 6	3 3 1 2
8 3 5 8 3 7 3 5 7 0 2 3 3	5 5 8
10 4 6 3 7 3 8 4 7 4 6 15 4 6 8 9	3 3 4 4
5 5 1 2 3 4 5 1 2 3 4 5	1 2 3 4 5
11 5 4 6 8 9 5 3 6 8 10 12 13 6 7 8 9 10	3 4 5 6 6

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] nums = new int[m];
        for(int i = 0; i < m; i++){
            nums[i] = sc.nextInt();
        }
        TreeMap<Integer, Integer> blackBox = new TreeMap<>();
        blackBox.put(Integer.MAX_VALUE, 1);
        int size = 1;
        int curKey = Integer.MAX_VALUE;
        int curValue = 1;
        int curPosition = 0;
        for(int i = 0; i < n; i++){
            int req = sc.nextInt();
            for(int j = size - 1; j < req; j++){
                if (blackBox.containsKey(nums[j])) {
                    blackBox.put(nums[j], blackBox.get(nums[j]) + 1);
                    if (curKey == nums[j]) {
                        curValue++;
                    }
                }
                else {
                    blackBox.put(nums[j], 1);
                }
                if(nums[j] < curKey) {
                    if (curPosition == 0) {
                        Map.Entry<Integer, Integer> curEnrty= blackBox.lowerEntry(curKey);
                        curKey = curEnrty.getKey();
                        curValue = curEnrty.getValue();
                        curPosition = curValue - 1;
                    }
                    else {
                        curPosition--;
                    }
                }
            }
            size = req + 1;
            System.out.println(curKey);
            if (curPosition == curValue - 1) {
                Map.Entry<Integer, Integer> curEnrty = blackBox.higherEntry(curKey);
                curKey = curEnrty.getKey();
                curValue = curEnrty.getValue();
                curPosition = 0;
            }
            else {
                curPosition++;
            }
        }
    }
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Map;

import java.util.Scanner;

import java.util.TreeMap;

public class Main {

public static void main(String[] args) throws Exception{

Scanner sc = new Scanner(System.in);

int m = sc.nextInt();

int n = sc.nextInt();

int[] nums = new int[m];

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

nums[i] = sc.nextInt();

}

TreeMap<Integer, Integer> blackBox = new TreeMap<>();

blackBox.put(Integer.MAX_VALUE, 1);

int size = 1;

int curKey = Integer.MAX_VALUE;

int curValue = 1;

int curPosition = 0;

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

int req = sc.nextInt();

for(int j = size - 1; j < req; j++){

if (blackBox.containsKey(nums[j])) {

blackBox.put(nums[j], blackBox.get(nums[j]) + 1);

if (curKey == nums[j]) {

curValue++;

}

else {

blackBox.put(nums[j], 1);

}

if(nums[j] < curKey) {

if (curPosition == 0) {

Map.Entry<Integer, Integer> curEnrty= blackBox.lowerEntry(curKey);

curKey = curEnrty.getKey();

curValue = curEnrty.getValue();

curPosition = curValue - 1;

}

else {

curPosition--;

}

size = req + 1;

System.out.println(curKey);

if (curPosition == curValue - 1) {

Map.Entry<Integer, Integer> curEnrty = blackBox.higherEntry(curKey);

curKey = curEnrty.getKey();

curValue = curEnrty.getValue();

curPosition = 0;

}

else {

curPosition++;

}

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

В следствие того, что в JCF нет мультисета, реализуем необходимые нам его функции (а именно итерирование) на базе TreeSet, ключами которого будут уникальные значения, хранящиеся в черном ящике, а значениями — количество раз, которое это значение содержится в черном ящике. При чтении очередного запроса добавляем соответствующие элементы в черный ящик, итерируясь вниз в случае добавления меньшего элемента чем текущий, и итерируемся вверх после каждого запроса.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

№	Ввод	Вывод
1	3 1 3 2	0
2	2 2 1	1
3	4 4 1 5 3	3
4	6 23 5 56 2 87 3	1
5	7 15 1 6 3 9 8 13	4

java@Cat

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

Tag Archives: минимальный элемент

e-olymp 2662. Метод минимума

Условие задачи

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

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

Тесты

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

Решение

Ссылки

e-olymp 1225. Черный Ящик

Задача

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

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

Тесты

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

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

Ссылки