I was following the 12hr stream of tmwilliamlin168 solving 150 problems from CSES. In the problem https://cses.fi/problemset/task/1631/ , I did'nt understood why answer is max(sum of elements, 2*last element); (He doing the same problem at https://youtu.be/dZ_6MS14Mg4?t=5237 with Timestamp);
→ Обратите внимание
До соревнования
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 15.10.2026 05:58:09 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
First let's sort the array such as x1 <= x2 <=x_3......<=x_n First Case: 2*x_n>=sum x_n>= sum-x_n =(x_1+x_2+x_3...+x_(n-1)) , it is optimal that the first person will read the first n-1 books , he will finish first and wait until the second person read the last book , then the first person will read the last book and the other will read the remaining books , this will take in total 2*x_n . Second case: sum>=2*x_n x_n<=sum-x_n the first person will read the books in this order n 1 2 3 4 5 .... n-1 the second person will read the books in this order 1 2 ........ n we can easily prove that no book will be read in this time. this will take in total the sum of all elements so the answer=max(sum,2*x_n)
I didn't understand second case. If first person reads in this order: "n 1 2 3 .... n-1" and second person reads in this order "1 2 3 ...n". How the times don't overlap?
The reason is $$$x_n+x_1+..+x_{k-1} \gt =x_1+x_2+...+x_k$$$; and $$$x_1+..+x_{n-1} \gt = x_n.$$$ It means that the first person always can read the book $$$k$$$ after finishing the book $$$k-1$$$, since the second person already finished reading it. Also, the second inequality shows that when the second person wants to read the last book, this book is already available. So the minimum reading time in this case is $$$x_1+...+x_n$$$.
thanks for wonderful explanation!
how would it affect the solution if in place of 2 persons, there were k persons?
sort the reading times ,WLOG Let x1<=x2<=...<=xn. If inequality x1+x2+...xn-1<(k-1)*xn holds then solution is k*xn else x1+x2+...+xn, Observe, this inequality is valid when k=2 as well.