[JAVA] problème atcoder ABC115 C

Notez la solution au problème ABC115 C C'était une simple question de tri normalement. https://atcoder.jp/contests/abc115/tasks/abc115_c

Façon de penser

Le problème de choisir K parmi un grand nombre d'arbres et de faire la plus petite différence entre les hauteurs maximales et minimales des arbres. Étant donné que le nombre d'arbres comprend jusqu'à 6 chiffres, si vous essayez jusqu'au bout, ce sera TLE avec une marge. De plus, le sentiment qu'il peut être résolu avec O (N) est incroyable. Étant donné que la différence entre le plus grand arbre et le plus petit arbre est tirée des K livres, si vous triez et prenez K livres dans l'ordre croissant, tournez-le vers le nième arbre avec for et update ans, vous pouvez obtenir la réponse. remarquer


int ans = 1000000000;
for(int i = 0;i + k - 1 < n;i++){
  int kari = h[i + k - 1] - h[i];       //Le maximum et le minimum sont clairs car ils sont triés
  ans = Math.min(ans, kari);
}

Recommended Posts

Problème atcoder ABC113 C

problème atcoder ABC115 C

AtCoder Beginner Contest 167 Problème C (Java)

ABC --013-A et B et C

ABC --023 --A & B & C

ABC --036-A et B et C

ABC --010 --A & B & C

ABC --028 --A & B & C

ABC --015 --A & B & C

ABC --128 --A & B & C

ABC --012-A et B et C

ABC --018 --A & B & C

AtCoder ABC 169 C virgule flottante qui tient dans Ruby

ABC --054 --A & B & C

ABC --017 --A & B & C

ABC --022 --A & B & C

ABC --019 --A & B & C

ABC --020 --A & B & C

ABC --127 --A & B & C

ABC --007 --A & B & C

ABC --132- A & B & C

ABC --026 --A & B & C

ABC --014- A & B & C

ABC --011-A et B et C

ABC --031 --A & B & C

ABC --021 --A & B & C

ABC --025 --A & B & C

ABC --024 --A & B & C

ABC --027 --A & B & C

ABC --080- A & B & C

Résolution avec Ruby, Perl et Java AtCoder ABC 128 C

ABC --129- A & B & C & D

ABC --133- A & B & C & D

ABC --122 --A & B & C & D

AtCoder Débutant Contest 132 D Problème

ABC --125- A & B & C & D

ABC --130- A & B & C & D

ABC --126 --A & B & C & D

Résolution avec Ruby, Perl et Java AtCoder ABC 113 C Reference

Résolution avec Ruby, Perl et Java AtCoder ABC 129 C (Partie 1)

ABC --134- A & B & C & D & E

ABC --131- A & B & C & D & E

Résolution avec Ruby, Perl et Java AtCoder ABC 129 C (Partie 2) Méthode de planification dynamique

Résolution avec Ruby AtCoder ABC177 D Union Find

Getter, Setter Reverse Problem-10 [Exemple de refactoring C #]

Briser de force le problème C "* 3 ou / 2" de [AtCoder Problem-ABC100] avec Java [Code]