Binary search

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

/* 첫 번째 줄에는 마을 수 N(1≤N≤100,000, 정수)이 입력된다 두 번째 줄부터 N줄에 걸쳐 마을 정보가 입력된다. 마을 정보는 두 개의 정수A, B이며 공백으로 구분되어 입력된다. A는 도시의 위치이며 B는 잡힌 물고기 양이다. (1≤A≤1,000,000,000, 단위는 km) (0≤B≤1,000,000,000, 단위는 톤) 마을 정보는 도로 위치에 따라 오름차순으로 정렬되어 입력된다. */   #include <stdio.h> #define _CRT_NO_SECURE_WARNINGS #define MAX 100000   int N = 0, maps[2][MAX + 1];   int isEnough(long long m) {     int i;     long long next=0, tax;       // 남는 양을 이웃 마을에 넘겨주기     // 만약, 거리가 너무 넓어서 넘겨줄 수 없는 경우 이웃에게 줄 수 있는 양은 0개     for (i = 0; i < N - 1; i++) {         long long sum = maps[1][i] + next - m; // 현재 마을의 물고기 양         long long tax = maps[0][i + 1] - maps[0][i];         if (sum>=0) {             if (sum - tax>=0)                 next = sum - tax;             else next = 0;         }         else             next = sum - tax;     }     if (maps[1][N-1]+next>= m) return 1;     else return 0; }   long long binary_upper_search(long long s, long long e) {     long long m, sol;     while(s<=e){          m = (s + e) / 2;         // 모든 마을에 m명의 아이들을 배정하고도 생선이 남는 경우         // 상한을 구해야 하므로 배정할 아이들의 수를 구한다.         if (isEnough(m)) {             sol = m;             s = m + 1;         }         // 아이들에게 생선을 나눠줄 수 없으면 배정할 아이들을 줄인다.         else e = m - 1;     }     return sol; }   int main(void) {     //freopen("input.txt", "r", stdin);     scanf("%d", &N);     int i;     long long max_fish = 0;     for (i = 0; i < N; i++) {         scanf("%d", &maps[0][i]);         scanf("%d", &maps[1][i]);         if (max_fish < maps[1][i]) max_fish = maps[1][i];     }           printf("%lld", binary_upper_search(0, max_fish));     return 0; }     /**************************************************************     Problem: 2740     User: AXQ6548     Language: C     Result: Accepted     Time:47 ms     Memory:1864 kb ****************************************************************/