Bài toán đoạn đường đẹp nhất:

[hai6f2009]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Cư dân thành phố XYZ vừa thành lập những con đường mới đẹp nhất thành phố. Theo các chuyên gia 1 con đường được coi là đẹp khi chiều cao TB của các toà nhà bằng K. Có n toà nhà, toà nhà thứ i có chiều cao là a
Yêu cầu: Tìm đoạn đường đẹp nhất đó
Dữ liệu vào: được cho trong file road.inp gồm:
dòng 1: ghi 2 số n,k (1<=n<=100000; 0<=k<=1000000000)
N dòng tiếp theo: dòng i ghi số nguyên a(0<=a<=1000000000)
Dữ liệu ra: Nếu không tìm được đoạn đường nào bằng k thì ghi 1 số 0. Ngược lại ghi ra 2 số u,v lần lượt là vị trí bắt đầu đoạn đường và độ dài đoạn đường. Nếu bài toán có nhiều kết quả thì cho kết quả có u nhỏ nhất.
ví dụ:
ROAD.INP
4 5
2
4
5
6
ROAD.OUT
2 3

 

[mikelhpdatke]

Bài toán tìm dãy con liên tiếp dài nhất sao cho tổng = k

Duyệt là cách đơn giản nhất

 

[hai6f2009]

re:trả lời bài toán đoạn đường đẹp nhất:

Mình cũng nghĩ là vậy nhưng khi mình viết code thì chạy toàn bị sai, bạn có thể coi giúp mình xem chỗ nào sai không?

program niceroad;
const   fi='road.inp';
        fo='road.out';
        max=100000;
var     f:text;
        n,k,minu,minv:int64;
        a:array[1..max] of int64;
        u,v,s:array[1..max] of int64;
procedure enter;
var i:integer;
begin
 assign(f,fi);reset(f);
 readln(f,n,k);
 for i:=1 to n do readln(f,a[i]);
 close(f);
end;

function min(x,y:integer):integer;
var b:integer;
begin
 min:=u[x];
 for b:=x to y do
  if u[b]<min then min:=u[b];
end;

procedure process;
var i,j,l:integer;
begin
 for i:=1 to n do
  begin
   a[i]:=a[i]-k;
   u[i]:=i;
  end;
 for i:=1 to n-1 do
   for j:=n downto 2 do
    begin
    for l:=i to j do
     begin
       s[i]:=s[i]+a[l];
       inc(v[i]);
     end;
    if s[i]=0 then
        begin
         minu:=min(i,j);
         minv:=v[i];
        end;
  end;
end;

procedure printresult;
begin
 assign(f,fo);rewrite(f);
 writeln(f,minu,' ',minv);
 close(f);
end;

BEGIN
 enter;
 process;
 printresult;
END.