AtCoder Beginner Contest 094 Revue des questions précédentes

Temps requis

Impressions

Étant donné que j'y étais auparavant, c'est la question à venir. Je peux répondre complètement si c'est à ce niveau, mais je veux être capable de rivaliser fermement avec quelque chose à un niveau légèrement supérieur.

Problème A

Notez qu'il faut que a <= x ainsi que a + b> = x.

answerA.py

a,b,c,d=[int(input()) for i in range(4)]
print(min(a,b)+min(c,d))

Problème B

Considérez le nombre de cabines de péage pour 1 ~ x et x ~ n respectivement. Si vous comptez le nombre de cabines de péage de 1 à x, vous pouvez également trouver le nombre de cabines de péage de x à n.

answerB.py

n,m,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in a:
    if i<x:
        ans+=1
    else:
        break
print(min(ans,m-ans))

Problème C

Concernant la valeur médiane, puisque n est un nombre pair, le n // 2e nombre ou le n // 2 + 1er nombre sera la valeur médiane lorsque les nombres 1 à n sont numérotés par ordre croissant. Si le n // 2e nombre est omis du 1er, le n // 2 + 1e nombre sera la valeur médiane, et si le n // 2 + 1er au nième nombre est omis, n /// Le deuxième nombre est la médiane. (** J'ai fait une expérience et je l'ai confirmée. **)

answerC.py

n=int(input())
x=list(map(int,input().split()))
y=sorted(x)
k,l=y[n//2-1],y[n//2]
for i in range(n):
    if x[i]<=k:
        print(l)
    else:
        print(k)

Problème D

Premièrement, pour $ \ _ {a_i} C \ _ {a_j} $, il est clair que lorsque vous corrigez ** $ a \ _j $, plus $ a \ _i $ est grand, plus gros **. Par conséquent, ** $ a \ _i $ est déterminé comme étant le plus grand de a **, il est donc seulement nécessaire de déterminer une variable de ** $ a \ _j $ **. Par conséquent, si vous calculez les éléments d'un autre que max (a) comme $ a_j $ dans $ \ _ {max (a)} C \ _ {a_j} $ et comparez leurs grandeurs, la valeur maximale est O (n). Il y a un piège ici, bien qu'il semble être recherché. En effet, ** $ \ _ {max (a)} C \ _r $ ne peut pas être calculé avec O (1) **. De plus, si vous créez un tableau pour le calcul de combinaison, il sera calculé par O (1), mais il faudra O (n) pour préparer le tableau, donc il ne sera pas à temps (n est jusqu'à 10 $ ^ 9 $). Par conséquent, si vous calculez $ \ _ {max (a)} C_r $, vous constaterez que vous ne pouvez pas respecter le délai. Maintenant, pensons à trouver $ a_j $ quand ** $ \ _ {max (a)} C \ _ {a_j} $ est le maximum sans calculer **. Ensuite, vous pouvez voir que $ a_j $ est maximisé aussi près de n / 2 que possible (je vais omettre la preuve car c'est un problème, mais c'est difficile à prouver en utilisant $ \ _nC \ _r = \ _nC \ _ {nr} $ Ça ne ressemble pas à ça.) Par conséquent, la réponse est l'élément d'un max (a) excluant qui est le plus proche de max (a) / 2. Cela nous a permis de trouver $ \ _nC \ _r $ sans le calculer. Après avoir implémenté ce qui précède, le code est le suivant.

answerD.py

n=int(input())
a=sorted(list(map(int,input().split())))
b=a[n-1]
a.pop(n-1)
ans=0
for i in range(n-1):
    if abs(b/2-a[ans])>abs(b/2-a[i]):
        ans=i
print(str(b)+" "+str(a[ans]))