Bỏ qua đến nội dung

Hướng giải: ANT

ANT

Mã bài: free038 Nhóm: Uncategorized Điểm: 100 điểm
Giới hạn
1,0 s, 256 MB
Tỉ lệ AC
30,8%
Người giải
4
Chỉ đọc hướng giải khi bế tắc và đừng sao chép mã trong đó. Hãy tôn trọng người ra đề và người viết hướng giải: nộp lời giải chính thức khi chưa tự giải được bài có thể khiến bạn bị khóa tài khoản.

Tóm tắt đề: cho n số nguyên được sắp xếp không giảm, với mỗi truy vấn là 2 số nguyên L và R hãy đếm số vị trí mà tổng độ chênh lệch là nhỏ nhất (độ chênh lệch của 2 số nguyên a và b là |a - b|).

Chia làm 2 trường hợp:

  • R - L + 1 là một số lẻ (độ dài của truy vấn là một số lẻ). Đáp án sẽ luôn là 1 (là vị trí a_{(R-L+2)/2}).
  • R - L + 1 là một số chẵn (độ dài của truy vấn là số chẵn). Đáp án sẽ là a_{(R-L+1)/2+1} - a_{(R-L+1)/2}+1.

Bình luận