Beachten Sie die Lösung für das ABC115 C-Problem Es war eine einfache Sache, normal zu sortieren. https://atcoder.jp/contests/abc115/tasks/abc115_c
Das Problem, K aus einer großen Anzahl von Bäumen auszuwählen und den Unterschied zwischen der maximalen und der minimalen Baumhöhe am kleinsten zu machen. Da die Anzahl der Bäume bis zu 6 Stellen beträgt, wird TLE mit einem Rand angezeigt, wenn Sie es vollständig versuchen. Auch das Gefühl, dass es mit O (N) gelöst werden kann, ist erstaunlich. Wenn man bedenkt, dass der Unterschied zwischen dem größten und dem kleinsten Baum aus den K-Büchern stammt, kann man die Antwort erhalten, wenn man K-Bücher in aufsteigender Reihenfolge sortiert und nimmt und sie in den n-ten Baum mit for und update ans dreht. beachten
int ans = 1000000000;
for(int i = 0;i + k - 1 < n;i++){
int kari = h[i + k - 1] - h[i]; //Das Maximum und das Minimum sind klar, weil sie sortiert sind
ans = Math.min(ans, kari);
}
Recommended Posts