Câu 3 thanh chương 2003

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: CHIADOAN.INP
Output: CHIADOAN.OUT

Dạng bài

Bài 3: (5 điểm)

Cho một dãy số gồm N phần tử nguyên dương và cặp số L và R (1<=L<R<=N). Em hãy chia đoạn con từ L đến R thành hai phần sao cho tổng chênh lệch giữa hai phần của mỗi đoạn con là nhỏ nhất. Biết rằng hai phần này là tổng của các số nằm liên tiếp với nhau trong đoạn con đó.</p>

Dữ liệu vào: File văn bản CHIADOAN.INP gồm:

  • Dòng 1 chứa hai số nguyên N, Q (1<N<=10^5; 1<Q<=10^5)</p>

  • Dòng 2 gồm N số nguyên dương ai (ai <=10^9, 1<i<=N)</p>

  • Q dòng tiếp theo, mỗi dòng gồm một cặp số nguyên L, R

Dữ liệu ra: File văn bản CHIADOAN.OUT gồm:

  • Gồm Q dòng, mỗi dòng là độ chênh lệch nhỏ nhất khi chia ra đoạn con tương ứng. Giới hạn:

  • Có 50% số test có N<= 1000 và Q <=1000

  • Có 50% số test còn lại không ràng buộc gì thêm

Giải thích:

  • Trong đoạn con thứ nhất [2,5] có cách chia ra đoạn [2,3] và đoạn [4,5] với tổng độ chênh lệch nhỏ nhất của 2 đoạn là: 2

  • Trong đoạn con thứ hai [1,4] có cách chia ra đoạn [1,1] và đoạn [2,4] với tổng độ chênh lệch nhỏ nhất của 2 đoạn là: 0


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.