/
BankQueue.java
executable file
·117 lines (84 loc) · 3.21 KB
/
BankQueue.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/**
* Fila do Banco
*
* Desafio:
* - O banco que você trabalha sempre tem problemas para organizar
* as filas de atendimento dos clientes.
*
* - Após uma reunião com a gerência ficou decidido que os clientes
* ao chegar na agência receberão uma senha numérica em seu aparelho
* de celular via sms e que a ordem da fila será dada não pela ordem
* de chegada, mas sim pelo número recebido via sms. Sendo, aqueles
* com número maior deverão ser atendidos primeiro.
*
* - Então, dada a ordem de chegada dos clientes reordene a fila de
* acordo com o número recebido via sms, e diga quantos clientes não
* precisaram trocar de lugar nessa reordenação.
*
* Entrada:
* - A primeira linha contém um inteiro N, indicando o número de casos
* de teste a seguir.
*
* - Cada caso de teste inicia com um inteiro M (1 ≤ M ≤ 1000), indicando
* o número de clientes. Em seguida haverá M inteiros distintos Pi
* (1 ≤ Pi ≤ 1000), onde o i-ésimo inteiro indica o número recebido via
* sms do i-ésimo cliente.
*
* - Os inteiros acima são dados em ordem de chegada, ou seja, o primeiro
* inteiro diz respeito ao primeiro cliente a chegar na fila, o segundo
* inteiro diz respeito ao segundo cliente, e assim sucessivamente.
*
* Saída:
* - Para cada caso de teste imprima uma linha, contendo um inteiro,
* indicando o número de clientes que não precisaram trocar de lugar
* mesmo após a fila ser reordenada.
*/
import java.io.IOException;
import java.util.*;
public class BankQueue {
private Integer smsNumber;
public BankQueue(int smsNumber) {
this.smsNumber = smsNumber;
}
public int getSmsNumber() {
return this.smsNumber;
}
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
scanner.nextLine();
int peopleOnQueue;
ArrayList<Integer> currentQueue = new ArrayList<>();
HashMap<Integer, Integer> numToIndexOriginal = new HashMap<>();
int currentSmsNumber;
int numSwitches;
for(int i = 0; i < N; i++) {
peopleOnQueue = scanner.nextInt();
numSwitches = 0;
for(int j = 0; j < peopleOnQueue; j++) {
currentSmsNumber = scanner.nextInt();
currentQueue.add(currentSmsNumber);
numToIndexOriginal.put(currentSmsNumber, currentQueue.size() - 1);
}
SmsNumberComparator comparator = new SmsNumberComparator();
Collections.sort(currentQueue, comparator);
for(int j = 0; j < currentQueue.size(); j++) {
int originalIndex = numToIndexOriginal.get(currentQueue.get(j));
if(originalIndex != j) {
numSwitches++;
}
}
System.out.println(peopleOnQueue - numSwitches);
currentQueue = new ArrayList<>();
}
scanner.close();
}
static class SmsNumberComparator implements Comparator<Integer> {
public SmsNumberComparator() {}
@Override
public int compare(Integer num0, Integer num1) {
int res = num0.compareTo(num1);
return -res;
}
}
}