Skip to content

Instantly share code, notes, and snippets.

@Phoenix124
Created January 20, 2018 15:54
Show Gist options
  • Save Phoenix124/8529c5e81631079676f898a19921f7ad to your computer and use it in GitHub Desktop.
Save Phoenix124/8529c5e81631079676f898a19921f7ad to your computer and use it in GitHub Desktop.
/*
* Тестовое задание:
N студентов стоят в очереди за стипендией. Каждый студент имеет учебный рейтинг. Деканат должен выдать стипендию таким образом, чтобы:
* каждый студент получил хотя бы 1 рубль,
* студенты с более высоким рейтингом получили больше рублей, чем их соседи в очереди.
Копеек в деканате нет. Какое минимальное количество рублей должно быть у деканата?
На вход подаётся массив из N элементов, содержащий рейтинги для каждого студента.
На выходе ожидается число, обозначающее минимальное количество рублей, которых должно хватить студентам.
Пример.
Вход: [1, 2, 3, 4, 5, 3, 2, 1, 2, 6, 5, 4, 3, 3, 2, 1, 1, 3, 3, 3, 4, 2]
Выход: 47
*/
import java.util.*;
public class TouchTest {
static class Student {
public Student(int id) {
this.id = id;
}
int id;
List<Student> moreThan = new ArrayList<>();
List<Student> lessThan = new ArrayList<>();
int pay = 0;
public String toString() {
return "Student{" +
"id=" + id +
", moreThan=" + moreThan +
'}';
}
}
public static void main(String[] args) {
Integer[] arr = {1, 2, 3, 4, 5, 3, 2, 1, 2, 6, 5, 4, 3, 3, 2, 1, 1, 3, 3, 3, 4, 2};
calculationSum(arr);
}
private static Set<Student> getMinorStudents(Collection<Student> students) {
Set<Student> set = new HashSet<>();
for (Student student : students) {
if (student.moreThan.isEmpty()) {
set.add(student);
}
}
return set;
}
private static void calculationSum(Integer[] arr) {
//создаем пул студентов
Map<Integer, Student> studentMap = new HashMap<>();
for (int j = 0; j < arr.length; j++) {
studentMap.put(j, new Student(j));
}
// строим отношения студентов
for (int i = 1; i < arr.length; i++) {
if (arr[i - 1] < arr[i]) {
studentMap.get(i - 1).lessThan.add(studentMap.get(i));
studentMap.get(i).moreThan.add(studentMap.get(i - 1));
}
if (arr[i - 1] > arr[i]) {
studentMap.get(i - 1).moreThan.add(studentMap.get(i));
studentMap.get(i).lessThan.add(studentMap.get(i - 1));
}
}
// текущая степендия (минимальная)
int currentPay = 1;
// студенты - с минимальной стипендией
Set<Student> currentPayStudents = getMinorStudents(studentMap.values());
while (!currentPayStudents.isEmpty()) {
Set<Student> nextPayStudents = new HashSet<>();
for (Student s : currentPayStudents) {
// стипендия студента = уровню если другая ветка не установила более высокую
s.pay = Math.max(s.pay, currentPay);
// студенты со степендией на уровень выше
nextPayStudents.addAll(s.lessThan);
}
// следующая итерация
currentPayStudents = nextPayStudents;
currentPay++;
}
// выводим стипендии и итоговую сумму
int sum = 0;
for (Student s : studentMap.values()) {
System.out.format("pay=%d, rate = %d \n", s.pay, arr[s.id]);
sum += s.pay;
}
System.out.format("итоговая сумма: %d", sum);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment