Created
January 20, 2018 15:54
-
-
Save Phoenix124/8529c5e81631079676f898a19921f7ad to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Тестовое задание: | |
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