Học sinh ham chơi

View as PDF

Submit solution


Points: 100 (partial)
Time limit: 10.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types

Hôm nay thầy giáo quyết định ra một bài tập về tính trung bình công cho cả lớp làm. Đề bài yêu cầu các bạn hãy tìm một dãy con liên tiếp sao cho trung bình cộng của dãy là lớn nhất có thể. T là một là một học sinh trong lớp, vì quá ham chơi, trốn học quá nhiều nên câu ta không giải được bài này nên cậu ấy đã quyết định nhờ các bạn giúp đỡ. Các bạn hãy giúp bạn ấy nhé!

Input

  • Dòng đầu tiên gồm một số nguyên dương N \ (1 \leq N \leq 10^5).
  • Dòng tiếp gồm N số nguyên dương x \ (1 \leq x \leq 10^5).

Output

Gồm một dòng duy nhất chính là kết quả của bài toán.

Sample Input

6
1 1 1 3 3 3

Sample Output

3

Giới hạn

  • 70% test có n \leq 5000
  • 30% test có n \leq 10^5

View comments (10)

Comments


  • 0
    huyhau6a2  commented on 8:24 p.m. 20 oct, 2022

    10s có hơi thừa không?


  • 1
    mikeyy  commented on 6:10 p.m. 14 aug, 2022

    Không giúp nha =)))


  • 0
    obitidev  commented on 2:36 p.m. 28 jul, 2022

    hình như admin ra đề mà quên để ý lỗ hổng trong đề sao ý. bài này khác gì tìm số lớn nhất trong mảng đâu ? 😂😂


    • 0
      tktungtd  commented on 2:51 p.m. 1 aug, 2022

      admin cố tình ra vậy mà bạn =)


  • 0
    tkvinhtruongquang  commented on 10:16 p.m. 8 oct, 2021

    thấy bài tập này sao sao ấy, nếu chỉ tính giá trị lớn nhất bằng đi tìm phần tử lớn nhất thì nó đôi lúc ko đúng, chẳng hạn như dãy 6 5 4 3 2 1 thì nếu chỉ lấy phần nguyên thì trung bình cộng dãy lớn nhất là 5 trong khi kết quả ra nếu làm theo thuật toán này sẽ là 6


    • 0
      VoBaThongL921  commented on 5:11 p.m. 20 oct, 2021

      chắc bạn có nhầm lẫn gì (hoặc mình nhầm:) ) thì dãy 6 5 4 3 2 1 của bạn thì dãy con có trung bình cộng lớn nhất là dãy có duy nhất 1 phần tử là 6 chứ. tbc của dãy là 6 / 1 = 6 đó bạn


      • 1
        longkold00  commented on 8:31 p.m. 22 oct, 2021

        bài này tìm max là đc e ới :v


        • 0
          VoBaThongL921  commented on 9:00 p.m. 22 oct, 2021

          Dạ đúng rồi ạ:)) mà em phải xem hint mới để ý lun á :v


  • -2
    donhatnam  commented on 9:13 a.m. 5 sep, 2020

    Tui chắc làm ngắn hơn ông


  • 8
    SPyofgame  commented on 12:51 p.m. 14 jun, 2020 edit 6

    Spoiler Alert


    Hint 1

    • Ta chỉ cần tìm max_a = max(\forall a_i \in a[]) của mảng

    Chứng minh: max_a \geq \frac{max_a * k}{k} \geq \frac{max(a_{i + 1} + a_{i + 2} + ... + a_{i + k}) * k}{k} \geq \frac{a_{i + 1} + a_{i + 2} + ... + a_{i + k}}{k}

    Reference AC code | O(n) time | O(1) auxiliary space | Online Solving

    int main()
    {
        int mx = 0;
        for (int n = readInt(); n--; mx = max(mx, readInt()));
        cout << mx;
        return 0;
    }