bài 1: làm phương pháp tham lam Có n ngôi làng được đánh số từ 1 đến n nằm trên một đường thẳng, ngôi làng thứ I nằm ở vị trí Ai (1≤ i≤n). Có một số ngôi làng có điện và những ngôi làng còn lại chưa có. Độ dài dây điện nối từ một ngôi làng i có điện đến ngôi làng j chưa có điện là |Ai-Aj|. Yêu cầu: Tính tổng độ dài dây nối ít nhất để tất cả các ngôi làng đều có điện. Dữ liệu vào: tệp KEODIEN.inp có cấu trúc như sau: Dòng đầu ghi số nguyên n (1≤ n ≤1.000). Dòng thứ hai ghi A1,A2, …,An, (0≤ A1 <A2,< …,<An ≤1.000.000). Dòng thứ ba ghi n số 0 hoặc 1 : nếu số thứ I là không nghĩa là làng này chưa có điện, ngược lại thì làng I đã có điện. Kết quả: ghi ra tệp KEODIEN.OUT ghi tổng độ dài dây nối ít nhất để mọi ngôi làng đều có điện. Ví dụ: KEODIEN.INP KEODIEN.OUT 3 5 1 5 6 1 0 0 bài 2: quy hoạch động Cần chia hết m phần thưởng cho n học sinh sắp theo thứ tự từ giỏi trở xuống sao cho mỗi bạn không nhận ít phần thưởng hơn bạn xếp sau mình. 1<= m, n<= 70. Hãy tính số cách chia. Thí dụ, với số phần thưởng m = 7, và số học sinh n = 4 sẽ có 11 cách chia 7 phần thưởng cho 4 học sinh theo yêu cầu của đầu bài. Đó là: Phương án 1 2 3 4 1 7 0 0 0 2 6 1 0 0 3 5 2 0 0 4 5 1 1 0 5 4 3 0 0 6 4 2 1 0 7 3 3 1 0 8 3 2 2 0 9 4 1 1 1 10 3 2 1 1 11 2 2 2 1 giải thích ý tưởng nha pascal :DD
2 câu trả lời
- Một số mà không cho biết làng nào thì cứ cho là 1 đi v:
- Nhận xét: Dù làng nào có điện thì các làng vẫn phải nối với nhau v:
`=>` Ta sắp xếp và tính tổng |a[i] - a[i + 1]| để tạo ra kết quả tối ưu nhất v:
- Code:
uses crt;
type int = longint;
var a: array[0..1000] of int;
i, n: int;
res: int64;
procedure sort(l, r: int);
var i, j, x, t: int;
begin
i:=l; j:=r; x:=a[(l + r) shr 1];
repeat
while a[i] < x do inc(i);
while x < a[j] do dec(j);
if i <= j then begin
t:=a[i]; a[i]:=a[j]; a[j]:=t;
inc(i); dec(j);
end;
until i > j;
if i < r then sort(i, r);
if l < j then sort(l, j);
end;
begin
clrscr;
readln(n);
for i:=1 to n do read(a[i]);
sort(1, n);
for i:=2 to n do inc(res, a[i] - a[i - 1]);
writeln(res);
readln;
end.
uses crt;
var f:text; i,n,j,t,kq:longint; a:array[1..1000]of longint;
begin
clrscr;
assign(f,'KEODIEN.inp');reset(f);
readln(f,n);
for i:=1 to n do read(f,a[i]);
close(f);
assign(f,'KEODIEN.out');rewrite(f);
for i:=1 to n do
for j:=i+1 to n do
if a[i]>a[j] then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end;
for i:=2 to n do kq:=kq+(a[i]-a[i-1]);
writeln(f,kq);
close(f);
end.
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết
- Đề thi học kì 2 môn địa 8 có lời giải chi tiết giúp các em luyện tập và củng cố kiến thức hiệu quả
- Kiểm tra 15 phút lần 1 học kì 1 - đề số 5 Địa 8 có lời giải chi tiết
- Kiểm tra 15 phút lần 1 học kì 1 - đề số 4 Địa 8 có lời giải chi tiết
