오랜만에 PS 문제를 풀었다. 해당 문제는 여기에서 확인할 수 있다.
갓갓류(rhs0266)의 추천으로 접하게 된 문제이다.
Parametric Search 를 이용해서 푸는 문제였는데, 다른 문제와는 다르게 어떤 조건으로 Binary Search 를 할 지가 키포인트였다.
사실 코드를 올리기 심히 부끄러우나, 그래도 로그삼아 올린다.
맞은 사람 중에서 등수는 3등인데 왜이런지 모르겠다 ㅋㅋㅋ
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
| #include<stdio.h> #define MAX 20001 #define INT_MAX 2147483647 int a[MAX], b[MAX], k[MAX], n; int getNum(int i, int limit) { if (limit < a[i]) return 0; int bb = b[i] > limit ? limit : b[i]; int x = (bb - a[i]) / k[i] + 1; return x; } long long int getNums(int limit) { long long int sum = 0; for (int i = 0; i < n; i++) { sum += getNum(i, limit); } return sum; } void p_search(long long int min, long long int max) { if (min >= max) { if (min == INT_MAX)printf("NOTHING\n"); else printf("%lld %lld", min, getNums(min) - getNums(min - 1)); return; } long long int med = (min + max) / 2; if (getNums(med) % 2 == 1) { p_search(min, med); } else { p_search(med + 1, max); } } int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d %d %d", &a[i], &b[i], &k[i]); } p_search(0, INT_MAX); return 0; }
|
첫 제출은 Wrong Answer 가 떴는데, 이는 med 값을 구할 때 med 를 int 로 선언하였는데
min + max 가 INT-MAX/2 + INT-MAX 가 될 수도 있어 오버플로우가 발생하였기 때문이다.
나처럼 long long int 로 바꿔도 되고, 그게 싫다면
1
| int med = min + (max - min) / 2;
|
이런 식으로 계산하면 int 범위 내에서 계산할 수 있을 것이다.