Chào mừng bạn đến với Selfomy Hỏi Đáp, hãy Hỏi bài tập hoặc Tham gia ngay
0 phiếu
311 lượt xem
trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)

Bưu cục

Có một số làng nằm dọc theo một đường cao tốc. Đường cao tốc được biểu diễn bằng một trục số nguyên và vị trí mỗi làng được xác định bởi một số nguyên duy nhất. Không có hai làng nào ở cùng một vị trí. Khoảng cách giữa hai vị trí bằng trị tuyệt đối của hiệu giữa hai toạ độ nguyên của chúng.

Một số bưu cục được xây dựng ở một số làng nhưng không nhất thiết tại mọi làng. Mỗi làng và bưu cục thuộc nó có cùng vị trí. Để xây dựng các bưu cục, vị trí của chúng cần chọn sao cho tổng các khoảng cách từ mỗi làng đến bưu cục gần nhất đối với làng đó là nhỏ nhất.

Bạn cần viết chương trình sao cho khi biết các vị trí của các làng và số lượng các bưu cục, hãy tìm tổng nhỏ nhất có thể được của các khoảng cách từ mỗi làng đến bưu cục gần nhất đối với nó và các vị trí tương ứng của các bưu cục.

Dữ liệu vào trong file POST.INP. Dòng thứ nhất chứa hai số gnuyên: số thứ nhất là số làng V, 1£V£300, số thứ hai là sốlượng bưu cục P, 1£P£30, P£V. Dòng thứ hai chứa V số nguyên theo thứ tự tăng dần, V số nguyên này là các vị trí của V làng. Với mỗi vị trí X, 1£X£10000

Dữ liệu ra trong file POST.OUT. Dòng thứ nhất chứa một số nguyên S là tổng nhỏ nhất có thể được của các khoảng cách từ mỗi làng đến bưu cục gần nhất đối với nó theo thông báo trong dòng thứ hai. Dòng thứ hai chứa P số nguyên theo thứ tự tăng dần. Các số nguyên này là các vị trí của các làng khác nhau tại đó đặt bưu cục. Có thể có một số lời giải, chương trình của bạn chỉ cần đưa ra một.

Ví dụ:

POST.INP

POST.OUT

10 5

1 2 3 6 7 9 11 22 44 50

9

2 7 22 44 50

 

 


1 Câu trả lời

0 phiếu
bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
 
Hay nhất
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+}
{$M 16384,0,655360}
{*********************************************************************
                             POST OFFICE
*********************************************************************}
uses crt;

const
   tfi='POST.INP';
   tfo='POST.OUT';
   maxV=300;
   maxP=30;

type
   mang=array[1..30] of LongInt;

var
   fi,fo: text;
   V,P: integer;
   d: array[1..maxV] of LongInt;
   a: array[1..maxV] of ^mang;
   Tr: array[1..maxV,1..maxP] of integer;
   S: LongInt;
   x: array[1..maxP] of integer;
   time: longint absolute 0:$046c;
   tsave: longint;

procedure Docdl;
var i: integer;
begin
   readln(fi,V,P);
   for i:=1 to V do read(fi,d[i]);
end;

function min(i,j: LongInt): LongInt;
begin
   if i end;

procedure XDB;
var i,j,k,l: integer;
    t: LongInt;
begin
   for i:=1 to maxV do new(a[i]);
   for i:=1 to V do
      begin
         a[i]^[1]:=0; Tr[i,1]:=0;
         for j:=1 to i-1 do a[i]^[1]:=a[i]^[1]+d[i]-d[j];
      end;
   for j:=2 to P do
      begin
         for i:=j to V do
            begin
               a[i]^[j]:=MaxLongInt;
               for k:=i-1 downto j-1 do
                  begin
                     t:=a[k]^[j-1];
                     for l:=k+1 to i-1 do
                        t:=t+min(d[l]-d[k],d[i]-d[l]);
                     if t                         begin
                           a[i]^[j]:=t;
                           tr[i,j]:=k;
                        end;
                  end;
            end;
      end;
end;

procedure XLB;
var i,j,u: integer;
    t: LongInt;
begin
   S:=MaxLongInt;
   for i:=P to V do
      begin
         t:=a[i]^[P];
         for j:=i+1 to V do t:=t+d[j]-d[i];
         if t             begin
               S:=t;
               u:=i;
            end;
      end;
   for i:=P downto 1 do
      begin
         x[i]:=u;
         u:=Tr[u,i];
      end;
end;

procedure Inkq;
var i: integer;
begin
   writeln(fo,S);
   for i:=1 to P do write(fo,d[x[i]],' ');
end;

BEGIN
   Tsave:=time;
   assign(fi,tfi); reset(fi);
   assign(fo,tfo); rewrite(fo);
   Docdl;
   XDB;
   XLB;
   Inkq;
   close(fi); close(fo);
   writeln('Tong thoi gian = ',(time-tsave)/18.3:0:2,' s');
END.

Các câu hỏi liên quan

0 phiếu
0 câu trả lời 448 lượt xem
Một vật dao động điều hòa dọc theo trục Ox. Tại thời điểm t vật đi qua vị trí có tốc độ với độ lớn gia tốc ... ;n tốc Biên độ dao động của vật có giá trị là bao nhiêu?
đã hỏi 10 tháng 6, 2021 trong Vật lý lớp 12 bởi trannhat900 ● Ban Quản Trị Phó giáo sư (52.9k điểm)
0 phiếu
1 trả lời 630 lượt xem
Có N người xếp hàng mua vé. Ta đánh số họ từ 1 đến N theo thứ tự đứng trong hàng. Thời gian phục vụ bán vé cho người thứ i là ti. ... qui ước ghi số 0) Ví dụ TICK.INP TICK.OUT 5 2 5 7 8 4 3 9 10 10 17 2 4
đã hỏi 2 tháng 2, 2021 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
1 trả lời 691 lượt xem
Có N khối đá hình hộp chữ nhật. Người ta muốn xây một cái tháp bằng cách chồng các khối đá này lên nhau. Để đảm bảo an toàn, các khối ... 1 5 4 2 7 2 9 2 1 3 3 5 5 5 4 1 5 7 5 9 5 5 5 5 5 5 1 4 2 4 2
đã hỏi 3 tháng 2, 2021 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
+1 thích
1 trả lời 507 lượt xem
Trên hai đường thẳng song song L1 và L2 người ta đánh dấu trên mỗi đường N điểm. Các điểm trên đường thẳng L1 được đánh ... ; tăng dần. Ví dụ: WIRES.INP WIRES.OUT 9 2 5 3 8 7 4 6 9 1 5 2 3 4 6 9
đã hỏi 3 tháng 2, 2021 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
1 trả lời 130 lượt xem
Một người sử dụng INTERNET đặt yêu cầu nhận thông tin về một số chủ đề khác nhau từ một số địa chỉ truy nhập. Chủ của các ... ;t nhất cần thực hiện. Ví dụ: EMAIL.INP EMAIL.OUT 7 1 3 4 3 2 2 3 4
đã hỏi 3 tháng 2, 2021 trong Tin học lớp 9 bởi thanhtrong ● Ban Quản Trị Thạc sĩ (6.2k điểm)
0 phiếu
1 trả lời 1.1k lượt xem
hãy giải thích tại sao hoang mạc lại phân bố nằm dọc hai đường chí tuyến và có vị trí sát với dòng biển lạnh
đã hỏi 8 tháng 12, 2016 trong Địa lý lớp 7 bởi hoihoi Học sinh (220 điểm)
0 phiếu
1 trả lời 855 lượt xem
Đồ thị vận tốc của một chất điểm chuyển động dọc theo trục Ox được biểu diễn như hình 5.4. Hãy xác định gia tốc của chất điểm trong các khoảng thời gian: 0–5s; 5–15s; >15s?
đã hỏi 10 tháng 7, 2021 trong Vật lý lớp 10 bởi manh7a1 ● Ban Quản Trị Tiến sĩ (18.9k điểm)
+1 thích
1 trả lời 402 lượt xem
Bài 1: Một tệp văn bản có tên là INP.TXT chứa đúng 2 số nguyên a,b. Tính tổng, hiệu, tích, thương của 2 số. Kết quả ghi ra tệp OUT.TXT
đã hỏi 1 tháng 4, 2022 trong Tin học lớp 11 bởi Khách
0 phiếu
1 trả lời 1.6k lượt xem
C1: Số hoàn thiện là số tự nhiên có tổng các ước của nó (không kể nó) bằng chính nó. VCT kiểm tra xem một số được nhập từ bàn phím có phải là số hoàn thiện không? C2: Một cửa hàng có các thùng sơn có cân nặng lần lượt là 16,17,21 kg. 1 người khách hàng cần mua 115kg. Hãy VCT tính và cho biết cần bán bao nhiêu thùng sơn mỗi loại mà không phải bán lẻ thùng nào?    
đã hỏi 1 tháng 12, 2017 trong Tin học lớp 8 bởi lop6/7tk_2017 Học sinh (314 điểm)

HOT 1 giờ qua

  1. nguyenmanh04102009212

    166 Điểm

  2. tnk11022006452

    120 Điểm

  3. hoconghung031007464

    80 Điểm

Phần thưởng hằng tháng
Hạng 1: 200.000 đồng
Hạng 2: 100.000 đồng
Hạng 3: 50.000 đồng
Hạng 4-10: 20.000 đồng
Bảng xếp hạng cập nhật 30 phút một lần
...