[PYTHON] Nombre moyen maximum de visiteurs quotidiens (grand)

0. Problème

Le nombre total de jours cible est JJ et vous visiterez pendant un certain N jours du nombre total de jours. Le nombre de dates candidates pour la date de début de la section où le nombre moyen de personnes est maximum, et parmi ces dates candidates Donnez le jour le plus tôt.

Voici un résumé de mes réflexions sur la résolution de ce problème. J'ai pu l'effacer par la procédure suivante.

1. Essayez d'abord de dessiner un diagramme

Les deux lignes suivantes sont données.

Nombre total de jours sur la première ligne(DD)Nombre de jours dans la section que vous souhaitez rechercher(N)\\
Nombre de visiteurs par jour sur la deuxième ligne(A_i(i=1,,,DD))

5 3 1 2 3 2 1

Pensant comme ci-dessus, Le deuxième jour de la date de début, le nombre de visiteurs quotidiens sera de huit, ce qui correspond à la section moyenne maximale. De plus, comme le nombre de visiteurs n'est maximisé que lorsque la date de début est de 2 jours, le nombre de jours candidats est Cela devient 1. Il s'avère que la réponse est "1 2".

2. Mode de pensée (division des modèles)

Ici, considérez que la moyenne est maximisée = la somme du nombre de visiteurs quotidiens dans une certaine section est maximisée.

«(1) Lorsque DD et N sont identiques»

⇒ Il n'est pas nécessaire de calculer le nombre de visiteurs à DD Puisqu'il n'y a qu'un seul modèle de date et de section candidat, [1 1] est la réponse.

(2) Lorsque DD> N et N> 1

X_1=A_1+...+A_{N}\\
max1=X_1(max1:Nombre maximum de visiteurs en N jours)\\
C_{day}=1(C_{day}:Nombre de jours candidats)\\
S_{day}=d(S_{day}:Date de début du nombre maximum de visiteurs en N jours)

X_d:Soit d le nombre de visiteurs pour N jours lorsque la date de début est
Du chapitre précédent, nous pouvons voir ce qui suit.
Cette formule de gradualisation peut également réduire le nombre de calculs.

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

ʻI) Nombre de visiteurs pour N jours avec une certaine date de début d> Traitement du nombre maximum de visiteurs`

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

ʻIi) Nombre de visiteurs pour N jours avec une certaine date de début d = Traitement du nombre maximum de visiteurs`

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

(3) Lorsque DD> N et N = 1

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

Considérons le traitement des conditions 1) et 2) dans le cas de (2) ci-dessus.

3. Exemple de code

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))