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.

0C94A4B5-A272-4603-A43D-1A638670F165.png

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

IMG-2991.jpg

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

Recommended Posts

Nombre moyen maximum de visiteurs quotidiens (grand)
Connectez un grand nombre de vidéos ensemble!
Téléchargez un grand nombre d'images sur Wordpress
Organisez un grand nombre de fichiers dans des dossiers
Accélérez un grand nombre de requêtes simples dans MySQL
[Python] Générer de manière aléatoire un grand nombre de noms de personne en anglais
Scrapy-Redis est recommandé pour l'exploration d'un grand nombre de domaines
Nombre maximum de caractères dans l'appel shell Python3 (par OS)