Advertisement
Guest User

Codeforces Round #303 (Div. 2), задача: (D) Очередь

a guest
Mar 21st, 2018
193
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.78 KB | None | 0 0
  1. /*
  2. D. Очередь
  3. ограничение по времени на тест 1 секунда
  4. ограничение по памяти на тест 256 мегабайт
  5.  
  6. Маленькая девочка Сьюзи ходила с мамой в магазин, и ей стало интересно, как можно улучшить обслуживание очередей.
  7.  
  8. В очереди стоит n людей. Для каждого человека известно время ti, необходимое на его обслуживание. Человек будет недоволен, если время его ожидания будет больше, чем время его обслуживания. Временем ожидания человека считается суммарное время обслуживания всех людей, стоящих перед ним в очереди. Сьюзи подумала, что если поменять местами некоторых людей в очереди, то получится уменьшить количество недовольных.
  9.  
  10. Помогите Сьюзи найти какого максимального количества довольных можно добиться, переставляя людей в очереди местами.
  11.  
  12. Входные данные
  13. В первой строке находится целое число n (1 ≤ n ≤ 105).
  14.  
  15. В следующей строке находятся n целых чисел ti (1 ≤ ti ≤ 109), разделенных пробелами.
  16.  
  17. Выходные данные
  18. Введите единственное число — максимальное количество довольных людей в очереди.
  19.  
  20. Примеры
  21. входные данныеСкопировать
  22. 5
  23. 15 2 1 5 3
  24. выходные данные
  25. 4
  26. Примечание
  27. Значение 4 достигается, например, при такой расстановке: 1, 2, 3, 5, 15. Таким образом можно сделать всех, кроме человека с временем 5, довольными.
  28. */
  29.  
  30. import java.io.IOException;
  31. import java.util.*;
  32.  
  33. public class Main{
  34.     public static void main (String args[]) throws IOException {
  35.         Scanner scan = new Scanner(System.in);
  36.         int n = scan.nextInt();
  37.         int arr[] = new int[n];
  38.         int sum = 0, cnt = 0;
  39.         for (int i = 0; i < n; i++) {
  40.             arr[i] = scan.nextInt();
  41.         }
  42.         Arrays.sort(arr);
  43.         for (int i = 0; i < n; i++) {
  44.                 if(arr[i]>=sum) {
  45.                     cnt++;
  46.                     sum += arr[i];
  47.                 }
  48.         }
  49.         System.out.println(cnt);
  50.     }
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement