AtCoder Beginner Contest 023 D 射撃王
考察
まず解法として最初に思い浮かんだのは、その時点の高さが最大の風船を割っていく貪欲だが、
風船iと風船jがあり、H[i] < H[j]で、S[i] > S[j]であると、ある時点では風船jの方が割られる風船だが、
最終的な高さは風船iの方が高くなる可能性があるので、貪欲では難しい。
こういう貪欲で最適な値を見つけるのには二分探索を使う。
二分探索で最小化する最大のペナルティを求める。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchElementException; public class Main { int N; int[] H,S; private static class Pair implements Comparable<Pair>{ int n; long v; public Pair(int n,long v){ this.n = n; this.v = v; } public int compareTo(Pair other){ if(this.v - other.v < 0){ return -1; }else if(this.v - other.v > 0){ return 1; } if(this.n - other.n < 0){ return -1; }else if(this.n - other.n > 0){ return 1; } return 0; } } public void solve() { N = nextInt(); H = new int[N]; S = new int[N]; for(int i = 0;i < N;i++){ H[i] = nextInt(); S[i] = nextInt(); } //最大値の最小値を二分探索で求める long left = 0L; long right = (long)1e17; while(right - left > 1){ long mid = ((left + right) >> 1); Pair[] p = new Pair[N]; for(int i = 0;i < N;i++){ // (mid - H[i]) / S[i] = i番目の風船がmidの高さにたどり着くために必要な秒数 // つまり、(mid - H[i]) / S[i]番目以内に割らなければならない p[i] = new Pair(i,(mid - H[i]) / S[i]); } Arrays.sort(p); boolean ok = true; for(int i = 0;i < N;i++){ // H[p[i].n] + S[p[i].n] * i = オーバーフロー // i番目の風船を割るときにペナルティが仮定した最大値midより大きければ、 // その最大値midは成り立たないので、もっとmidを大きくしなければならない if(H[p[i].n] + (long)S[p[i].n] * i > mid){ ok = false; break; } } if(ok){ right = mid; }else{ left = mid; } } out.println(right); } public static void main(String[] args) { out.flush(); new Main().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }