Có một dãy các số nguyên a1, a2, ..., an. Ta chia dãy số này thành 2 dãy con như sau: – Dãy con thứ nhất gồm k số đầu tiên trong dãy đã cho và tổng các phần t
Có một dãy các số nguyên a1, a2, ..., an. Ta chia dãy số này thành 2 dãy con như sau: – Dãy con thứ nhất gồm k số đầu tiên trong dãy đã cho và tổng các phần tử của dãy con này là T1. – Dãy con thứ hai gồm các số còn lại của dãy số đã cho và tổng các phần tử của dãy con này là T2. Yêu cầu: Tìm số nguyên dương k là độ dài của dãy con thứ nhất sao cho|T1-T2| nhỏ nhất. Chú ý: Nếu có hơn một số k thỏa mãn thì ghi ra số k nhỏ nhất. Cách làm: Tạo một mảng T[1..n] với T[i] = a1 + a2 + ... + ai. Xét hai dãy {a1, a2,...ak} có tổng là T1 và dãy {ak+1, ak+2, ...,an} có tổng là T2. Khi đó, ta có: T1 = T[k] và T2 = T[n] – T[k] => |T1 – T2|= |T[n] – 2*T[k]| Dùng vòng lặp để duyệt tất cả các biểu thức |T[n]–2T[i]| với . Trong các biểu thức có GTNN, ta chọn giá trị i nhỏ nhất là số cần tìm GIUP EM VOI A CAN GAP LAMMM
Lời giải 1 :
var i,n,t,s,min,k:longint; a:array[1..1000000] of longint;
begin
readln(n);
for i:=1 to n do begin read(a[i]); s:=s+a[i]; end;
min:=high(longint);
for i:=1 to n-1 do
begin
t:=t+a[i]; s:=s-a[i];
if abs(t-s)<min then begin k:=i; min:=abs(t-s); end;
if t=s then break;
end;
writeln(k);
end.
Thảo luận
Có thể bạn quan tâm
Bạn có biết?
Tin học, tiếng Anh: informatics, tiếng Pháp: informatique, là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng (ảo). Với cách hiểu hiện nay, tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin.
Nguồn : Wikipedia - Bách khoa toàn thưTâm sự 9
Lớp 9 - Là năm cuối ở cấp trung học cơ sở, sắp phải bước vào một kì thi căng thẳng và sắp chia tay bạn bè, thầy cô và cả kì vọng của phụ huynh ngày càng lớn mang tên "Lên cấp 3". Thật là áp lực nhưng các em hãy cứ tự tin vào bản thân là sẻ vượt qua nhé!
Nguồn : ADMIN :))Xem thêm tại https://loigiaisgk.com/cau-hoi or https://giaibtsgk.com/cau-hoi
Copyright © 2021 HOCTAPSGK