Editorial for Học sinh ham chơi

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: SPyofgame

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;
}

Comments


  • 0
    trieunguyen_a1  commented on 9:49 p.m. 11 sep, 2021

    không rõ lắm ạ có ai giảng nhẹ giúp em được không ạ ? Cảm ơn


    • 2
      VoBaThongL921  commented on 8:52 p.m. 22 sep, 2021

      Mình nghĩ là trung bình cộng của mọi dãy con đều bé hơn hoặc bằng phần tử lớn nhất trong mảng ấy. Vậy giá trị lớn nhất chính là phần tử lớn nhất đó, với dãy con có 1 phần tử là phần tử đó luôn