Tìm dãy tổng liên tiếp

Xem dạng PDF
Gửi bài giải
Điểm: 18,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho dãy số nguyên dương a có n phần tử. Hãy tìm độ dài đoạn con dài nhất trong dãy sao cho tổng các phần tử trong đoạn này không quá s. Dữ liệu đảm bảo các phần tử trong dãy a đều có giá trị không quá s.

Input:

  • Dòng 1. Ghi 2 số nguyên dương n, s.
  • Dòng 2. Ghi n số nguyên ~a_1, a_2,...,a_n~

Output:

  • Ghi ra độ dài của dãy con dài nhất thoả mãn yêu cầu trên.

Example:

Input:

7 20
2 6 5 3 6 8 9

Output:

4

Constraints:

~n \le 10^6; 0 \le a_i \le 10^9; s \le 10^{18}~

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    memaybeocomvn  đã bình luận lúc 15, Tháng 10, 2024, 9:55

    ............


  • -2
    Shinoz  đã bình luận lúc 26, Tháng 8, 2023, 15:20 ← chỉnh sửa

    Solution By Shinoz

    Hint 1 - Prefix Sum ( TLE )

    Chạy vòng lặp đọc các phần tử trong mảng và lưu vào mảng cộng dồn

    Chạy vòng lặp lồng để kiểm tra tổng từ i -> j có <= s hay không, nếu có lấy biến max lưu khoảng cách của i -> j (j - i + 1)

    Hint 2 - Two pointer ( AC )

    Lấy biến max = 0, sum = 0, j = 0

    Chạy vòng lặp i từ 1 -> n:

    Liên tục cập nhật tổng sum = sum + a[i]

    Nếu tổng sum > s thì ta cộng j lên 1 đơn vị và giảm tổng sum đi a[j] và cập nhật max = i - j

    Nếu bí quá có thể liên hệ mình để hỏi rõ và lấy code tại đây


    • -7
      ht_maths2512  đã bình luận lúc 26, Tháng 10, 2023, 11:55

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -1
        abcnickname  đã bình luận lúc 2, Tháng 10, 2024, 9:04

        ohno anh shinoz troll troll roi


        • -2
          abcnickname  đã bình luận lúc 3, Tháng 10, 2024, 8:11

          cái phần ma=i-j bị sai nha sau khi kết thức thì in ra i-j-1 >:)


      • -3
        EvolutionOfLearning  đã bình luận lúc 1, Tháng 12, 2023, 4:02

        skibidi dop dop yes yes


  • -10
    khoi1503  đã bình luận lúc 26, Tháng 8, 2023, 13:42

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.