Phát kẹo theo thứ hạng

Buổi 12 — Greedy Algorithm greedy Implementation
Points
33
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Có $N$ học sinh đứng thành một hàng ngang, học sinh thứ $i$ có điểm đánh giá $r_i$. Giáo viên muốn phát kẹo cho các học sinh theo hai quy tắc:

  1. Mỗi học sinh phải nhận được ít nhất $1$ viên kẹo.
  2. Nếu một học sinh có điểm đánh giá cao hơn hẳn học sinh đứng ngay cạnh mình, học sinh đó phải nhận được nhiều kẹo hơn người kia.

Hãy tìm tổng số viên kẹo ít nhất mà giáo viên cần chuẩn bị.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • Dòng thứ hai chứa $N$ số nguyên $r_1, r_2, \dots, r_N$.
Dữ liệu ra

Một số nguyên duy nhất là tổng số viên kẹo ít nhất cần chuẩn bị.

Ví dụ
Input Output
3\n1 0 2 5
3\n1 2 2 4
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le r_i \le 10^9$
Draft saved