[PYTHON] Maximale durchschnittliche Anzahl täglicher Besucher (groß)

0. Problem

Die angestrebte Gesamtzahl der Tage ist DD, und Sie werden während bestimmter N Tage der Gesamtzahl der Tage besuchen. Die Anzahl der Kandidatentermine für das Startdatum des Abschnitts, in dem die durchschnittliche Anzahl der Personen maximal ist, und unter diesen Kandidatenterminen Geben Sie den frühesten Tag.

Hier ist eine Zusammenfassung meiner Gedanken zur Lösung dieses Problems. Ich konnte es durch das folgende Verfahren löschen.

1. Versuchen Sie zuerst, ein Diagramm zu zeichnen

Die folgenden zwei Zeilen sind angegeben.

Gesamtzahl der Tage in der ersten Zeile(DD)Anzahl der Tage in dem Abschnitt, den Sie suchen möchten(N)\\
Anzahl der Besucher pro Tag in der zweiten Zeile(A_i(i=1,,,DD))

5 3 1 2 3 2 1

Denken wie oben, Am zweiten Tag des Startdatums beträgt die Anzahl der täglichen Besucher acht, was dem maximalen Durchschnittsabschnitt entspricht. Da die Anzahl der Besucher nur maximiert wird, wenn das Startdatum 2 Tage beträgt, beträgt die Anzahl der Kandidatentage Es wird 1. Es stellt sich heraus, dass die Antwort "1 2" ist.

2. Denkweise (Musterteilung)

Beachten Sie hier, dass der Durchschnitt maximiert ist = die Summe der Anzahl der täglichen Besucher in einem bestimmten Abschnitt wird maximiert.

"(1) Wenn DD und N gleich sind"

⇒ Die Anzahl der Besucher von DD muss nicht berechnet werden Da es nur ein Kandidatendatum und ein Schnittmuster gibt, ist [1 1] die Antwort.

"(2) Wenn DD> N und N> 1"

X_1=A_1+...+A_{N}\\
max1=X_1(max1:Maximale Besucherzahl in N Tagen)\\
C_{day}=1(C_{day}:Anzahl der Kandidatentage)\\
S_{day}=d(S_{day}:Startdatum der maximalen Besucherzahl in N Tagen)

X_d:Sei d die Anzahl der Besucher für N Tage, wenn das Startdatum ist
Aus dem vorherigen Kapitel können wir Folgendes sehen.
Diese Gradualisierungsformel kann auch die Anzahl der Berechnungen reduzieren.

X_d=X_{d-1}-A_{d-1}+A_{d-1+N}(d=2,,,DD-N+1)-★\\

"I) Anzahl der Besucher für N Tage mit einem bestimmten Startdatum d> Verarbeitung der maximalen Anzahl von Besuchern"

C_{day}=1\\
max1=X_d\\
S_{day}=d

"Ii) Anzahl der Besucher für N Tage mit einem bestimmten Startdatum d = Verarbeitung der maximalen Anzahl von Besuchern"

C_{day}=C_{day}+1\\
max1=X_d

"(3) Wenn DD> N und N = 1"

X_d=A_d(d=1,,,DD)

Betrachten Sie die Verarbeitung der Bedingungen 1) und 2) im Fall von (2) oben.

3. Codebeispiel

in1=input()
in2=input()
arr1=in1.split()
arr2=in2.split()

dn=0

num1=int(arr1[1])
#print(num1)

if num1>1:
    i=0
    for i in range(num1):
        dn=dn+int(arr2[i])

    max_t=dn
    max_i=0
    k_cnt=1

    for i in range(1,int(arr1[0])-num1+1):
        dn=dn+int(arr2[i+num1-1])-int(arr2[i-1])

        if max_t<dn:
            k_cnt=1
            max_i=i
            max_t=dn

        else:
            if max_t == dn:
                k_cnt=k_cnt+1
                max_t=dn

    max_i=max_i+1
    print(str(k_cnt)+' '+str(max_i))

elif num1>1 and num1 == int(arr1[0]):
    print('1 1')
else:
    max_i=0
    max_t=0
    k_cnt=1
    for i in range(int(arr1[0])):
        dn=int(arr2[i])
        if max_t<dn:
            max_t=dn
            k_cnt=1
            max_i=i
        else:
            if max_t == dn:
                max_t=dn
                k_cnt=k_cnt+1

    max_i=max_i+1
    print(str(k_cnt)+' '+str(max_i))