Balancing the Barns

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bác John quản lý $N$ chuồng bò trên một con đường. Chuồng thứ $i$ chứa $a_{i}$ bó cỏ khô và $b_{i}$ bao thức ăn.

Độ mất cân bằng được định nghĩa là: $max (a_{i}) - min (b_{i})$ trên tất cả các chuồng.

Bác John thực hiện đúng $K$ phép chuyển, mỗi phép chọn một chuồng $i$ , giảm $a_{i}$ đi 1 và tăng $b_{i}$ lên 1.

Hãy tìm độ mất cân bằng tối thiểu sau đúng $K$ phép chuyển.

Dòng đầu tiên chứa số nguyên $T$ ( $1 \leq T \leq 10^{3}$ ) - số test case.
Với mỗi test case:
- Dòng 1: Hai số nguyên $N$ ( $1 \leq N \leq 5 \times 10^{4}$ ) và $K$ ( $1 \leq K \leq 10^{18}$ ).
- Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ ( $0 \leq a_{i} \leq 10^{9}$ ).
- Dòng 3: $N$ số nguyên $b_{1}, b_{2}, \dots, b_{N}$ ( $0 \leq b_{i} \leq 10^{9}$ ).

Tổng $N$ trên tất cả test case không vượt quá $5 \times 10^{4}$ .

Với mỗi test case, in ra một số nguyên - độ mất cân bằng tối thiểu.

Input	Output	Giải thích
4 1 10 5 3 2 6 100 96 0 4 3 3 1 1 2 0 0 1 3 3 1 2 2 0 1 1	-18 90 0 0	Test case 1: 1 chuồng, 10 phép chuyển: a=5-10=-5, b=3+10=13, mất cân bằng = -5-13 = -18. Test case 3: chuyển 1 từ chuồng 3 (a3=1,b3=2), 1 từ chuồng 1 (a1=0,b1=1), 1 từ chuồng 2 (a2=0,b2=1) -> max(a)=0, min(b)=1, mất cân bằng=0-1<0, nhưng cần đúng 3 phép.

Bình luận

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