ICPC PNW 2016/Camera.java
From charlesreid1
Main article: ICPC PNW 2016
Code
import java.util.* ; public class Cameras { public static void main(String[] args) { Scanner sc = new Scanner(System.in) ; int N = sc.nextInt() ; int K = sc.nextInt() ; int R = sc.nextInt() ; boolean c[] = new boolean[N] ; for (int i=0; i<K; i++) c[sc.nextInt()-1] = true ; int mincam = 2 ; int r = 0 ; int s = 0 ; for (int i=0; i < c.length && i<R; i++) if (c[i]) s++ ; int pa = 0 ; int pb = R ; while (pb <= N) { int ca = pb - 1 ; while (s < mincam) { while (c[ca]) ca-- ; c[ca--] = true ; s++ ; r++ ; } if (pb >= N) break ; if (c[pa++]) s-- ; if (c[pb++]) s++ ; } System.out.println(r) ; } }
Explanation
This problem requires a greedy approach; scan through the consecutive sets of houses of width R, count the number of cameras already there, and if we don't have enough, add as many as needed as far right (towards the next sets of houses) as possible. It is easy to see that adding cameras as far right as possible maximizes their utility for subsequent sets. To keep the running count, we maintain a trailing and a forward pointer and calculate it incrementally; a quadratic solution will not run in time. int trail = 0 ; int lead = 0 ; int sum = 0 ; while (lead < R) // calculate number of cameras in initial set if (hascamera[lead++]) sum++ ; int r = 0 ; while (true) { for (int k=lead-1; sum<2; k--) // add cameras for this gap if (!hascamera[k]) { hascamera[k] = true ; r++ ; } if (lead >= N) // done? break ; if (hascamera[trail++]) // advance pointers sum-- ; if (hascamera[lead++]) sum++ ; }