kết quả từ 1 tới 7 trên 7

Dãy Con Lớn Nhất Có Độ Dài Như Nhau

  1. #1
    Ðến Từ
    Quảng Ninh
    Thành Viên Thứ: 369432
    Giới tính: Nữ
    Bài gửi
    3

    Question Dãy Con Lớn Nhất Có Độ Dài Như Nhau

    Dãy Con
    Cho dãy số nguyên A gồm n phần tử A[1],A[2],..,A[n] và một số nguyên dương d (1<= d <= n)
    Hãy tìm một đoạn con liên tiếp của dãy A có độ dài d và có tổng các phần tử đạt giá trị lớn nhất (độ dài của đoạn con là số lượng phần tử trên đoạn con đó).
    Yêu cầu :tính tổng các phần tử trên đoạn con theo yêu cầu như trên
    Dữ liệu vào : từ tệp DAYCON.INP có cấu trúc như sau
    - dòng thứ nhất chứa hai số nguyên dương n,d (1 <= d <= n <= 10^6)
    - dòng thứ hai chứa n số nguyên A[1],A[2],..,A[n] trong đó (A[i] <= 10^4,1 <= i <=n)
    Dữ liệu ra: Ghi vào tệp DAYCON.OUT gồm một số nguyên duy nhất là tổng các phần tử trên đoạn con tìm được có giá trị lớn nhất


    DAYCON.INP DAYCON.OUT
    5 3
    -4 3 -2 6 5
    9


    - Bài này mình vừa thi xong,mọi người giúp mình với
    - Mình không làm được bài này lúc thi,tiếc lắm,mong mọi người giúp ạ
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Dãy Con Lớn Nhất Có Độ Dài Như Nhau

    Bạn chỉ cần đọc d phần tử liên tiếp từ đầu tới cuối dãy. Khi đọc tới a[i] thì sum = sum + a[i] - a[i - d - 1] (lấy 1 phần tử mới và loại 1 phần tử cũ). Thuật toán có độ phức tạp O(n).
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. Đã cảm ơn tengiday:

    Ririka 

  4. #3
    Ðến Từ
    Quảng Ninh
    Thành Viên Thứ: 369432
    Giới tính: Nữ
    Bài gửi
    3

    Reply: Dãy Con Lớn Nhất Có Độ Dài Như Nhau

    Nhưng nếu với i=1 thì a[i-d-1] chẳng phải sẽ thành vị trí âm sao? Mình vẫn chưa hiểu lắm....

  5. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Dãy Con Lớn Nhất Có Độ Dài Như Nhau

    Trích Nguyên văn bởi Ririka Xem bài viết
    Nhưng nếu với i=1 thì a[i-d-1] chẳng phải sẽ thành vị trí âm sao? Mình vẫn chưa hiểu lắm....
    - Đầu tiên bạn tính tổng của d phần tử đầu tiên: a[1] + ... + a[d].
    - Sau đó cho 'for i := d + 1 to n' rồi tính 'sum = sum + a[i] - a[i - d - 1]'. Mỗi lần có tổng mới thì bạn so sánh với tổng max.

  6. Đã cảm ơn tengiday:

    Ririka 

  7. #5
    Ðến Từ
    Quảng Ninh
    Thành Viên Thứ: 369432
    Giới tính: Nữ
    Bài gửi
    3

    Reply: Dãy Con Lớn Nhất Có Độ Dài Như Nhau

    Trích Nguyên văn bởi tengiday Xem bài viết
    - Đầu tiên bạn tính tổng của d phần tử đầu tiên: a[1] + ... + a[d].
    - Sau đó cho 'for i := d + 1 to n' rồi tính 'sum = sum + a[i] - a[i - d - 1]'. Mỗi lần có tổng mới thì bạn so sánh với tổng max.
    - Mình làm được bài rồi,dễ hơn mình tưởng...
    - Cảm ơn bạn nhé

  8. Đã cảm ơn Ririka:


  9. #6
    Ðến Từ
    Thừa Thiên - Huế
    Thành Viên Thứ: 356879
    Giới tính: Nam
    Bài gửi
    50

    Reply: Dãy Con Lớn Nhất Có Độ Dài Như Nhau

    hình như sum:= sum+a[i] - a[i -d] phải không ak

  10. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Dãy Con Lớn Nhất Có Độ Dài Như Nhau

    Trích Nguyên văn bởi tuonglong Xem bài viết
    hình như sum:= sum+a[i] - a[i -d] phải không ak
    Uh, là a[i - d]. Mình ko check index kỹ; nắm ý chính "sliding window" là làm thôi.