Dãy số cân bằng
View as PDFCho dãy gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~. Ban dãy ~a~ thỏa mãn điều kiện ~a_1 \le 2\cdot a_i~ với mọi ~2 \le i \le n~. Đây được gọi là điều kiện cân bằng của dãy ~a~.
Được phép thực hiện dãy các tác sau không hoặc nhiều lần:
Chọn chỉ số ~i~ (~2 \le i \le n~) và số nguyên ~x~ sao cho ~x \le a_i~.
Thực hiện biến đổi ~a_1 \gets a_1 + x~ và ~a_i \gets a_i - x~.
Sau phép biến đổi, điều kiện cân bằng của mảng ~a~ phải được thỏa mãn.
~x~ được gọi là điểm số cho thao tác này.
Tìm tổng điểm số lớn nhất có thể sau khi thực hiện thao tác trên không hoặc nhiều lần.
Input
Bộ dữ liệu gồm nhiều test case. Dòng đầu tiên của bộ dữ liệu chứa số nguyên dương ~t~ (~1 \le t \le 100~) là số lượng test case. Mô tả của mỗi test case như sau.
Dòng đầu tiên chứa số nguyên ~n~ (~2 \le n \le 200\,000~) — độ dài dãy ~a~.
Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~, ~a_1 \le 2 a_i~ với mọi ~2 \le i \le n~).
Dữ liệu đảm bảo rằng tổng ~n~ trong tất cả các test case không quá ~2 \cdot 10^5~.
Output
Với mỗi test case, hãy in ra tổng điểm số tối đa có thể đạt được sau khi thực hiện thao tác không hoặc vài lần.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~250~ | ~n \le 100~, ~a_i \le 100~ |
| 2 | ~250~ | Không có ràng buộc gì thêm |
| Tổng | ~500~ |
Sample Input 1
3
3
2 3 4
2
1 11
4
5 3 3 3
Sample Output 1
2
7
0
Notes
Với testcase thứ nhất, tổng điểm số tối đa có thể đạt được là ~2~:
ta có ~x = 1~ điểm khi chọn ~i = 2~. Lúc này ta có dãy ~a = [3, 2, 4]~
ta có ~x = 1~ điểm khi chọn ~i = 3~. Lúc này ta có dãy ~a = [4, 2, 3]~.
Với testcase thứ hai, tổng số điểm ta có thể đạt được là ~7~ bằng cách chuyển ~x = 7~ điểm từ vị trí ~i = 2~. Ta thu được dãy ~a = [8, 4]~.
Ở test case thứ ba, ta không có cách tăng điểm nào để thỏa mãn điều kiện cân bằng của dãy ~a~.
Comments
Các đại lão giúp em với, sao code của em full sub 2 mà sai hết sub 1 ạ
include<bits/stdc++.h>
define endl '\n'
using namespace std; typedef long long ll; ll t,n,i,x,a1,res,mi,ma; ll sum; int main() { iosbase::syncwithstdio(0); cin.tie(0);cout.tie(0); cin>>t; while(t--) { sum=0;mi=INTMAX;ma=0; cin>>n; cin>>a1; for(i=1;i<n;i++) { cin>>res; sum+=res; if(res<mi)mi=res; if(res>ma)ma=res; } sum-=(1LLmi(n-1)); x=2*mi-a1; if(n==2) { cout<<x/3<
>