atcoder ABC115 C problem

Make a note of how to solve the ABC115 C problem It was a simple matter of sorting normally. https://atcoder.jp/contests/abc115/tasks/abc115_c

Way of thinking

The problem of choosing K from a large number of trees and making the difference between the maximum and minimum tree heights the smallest. Since the number of trees is up to 6 digits, if you try all the way, it will be TLE with a margin. Also, the feeling that it can be solved with O (N) is amazing. Considering that the difference between the largest tree and the smallest tree is taken from the K books, if you sort and take K books in ascending order, turn it to the nth tree with for, and update ans, you can get the answer. notice


int ans = 1000000000;
for(int i = 0;i + k - 1 < n;i++){
  int kari = h[i + k - 1] - h[i];       //The maximum and minimum are clear because they are sorted
  ans = Math.min(ans, kari);
}

Recommended Posts

atcoder ABC113 C problem
atcoder ABC115 C problem
AtCoder Beginner Contest 167 C Problem (Java)
ABC --013-A & B & C
ABC --023 --A & B & C
ABC --036-A & B & C
ABC --010 --A & B & C
ABC --028 --A & B & C
ABC --015 --A & B & C
ABC --128 --A & B & C
ABC --012-A & B & C
ABC --018 --A & B & C
AtCoder ABC 169 C Floating Point Fits in 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 & B & 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
Solving with Ruby, Perl and Java AtCoder ABC 128 C
ABC --129- A & B & C & D
ABC --133- A & B & C & D
ABC --122 --A & B & C & D
AtCoder Beginner Contest 132 D Problem
ABC --125- A & B & C & D
ABC --130- A & B & C & D
ABC --126 --A & B & C & D
Solving in Ruby, Perl and Java AtCoder ABC 113 C Reference
Solving with Ruby, Perl and Java AtCoder ABC 129 C (Part 1)
ABC --134- A & B & C & D & E
ABC --131- A & B & C & D & E
Solving with Ruby, Perl and Java AtCoder ABC 129 C (Part 2) Dynamic programming
Solve with Ruby AtCoder ABC177 D UnionFind
Getter, Setter Inverse Problem-10 [C # Refactoring Sample]
[Code] Forcibly breaks through the C problem "* 3 or / 2" of [AtCoder Problem-ABC100] with Java [Code]