이분탐색10 BOJ 2261 - 가장 가까운 두 점 (라인스위핑) https://www.acmicpc.net/problem/2261 https://www.acmicpc.net/blog/view/25 위 링크의 백준님이 설명해주신 방법 리뷰 좌표평면 위에 최대 n개의 좌표 x,y가 주어질 때, 가장 가까운 두 점의 거리의 제곱을 구해라 (n> p[i].first >> p[i].second; sort(p, p + n); ll st = 0, ans = 2e18; set cand; cand.insert(p[0]); for (ll i = 1,x,y; i ans) { cand.erase(p[st]); st++; } else.. 2020. 5. 19. cf 562 div2 C - Increasing by modulo (이분탐색, 그리디) https://codeforces.com/contest/1169/problem/C 0~m사이 값을 갖는 n개의 요소를 갖는 배열이 주어진다. 임의의 배열 요소을 여러개 골라 (ai+1) % m해주는 것을 하나의 operation이라 할때, 배열 a를 단조증가로 만들기 위해선 최소 몇번의 operation을 해야 하는가? 최소 0번 최대 m번의 operation이 필요하다. 어떤횟수 이상의 operation을 수행하면 정렬이되므로 이분탐색. bool pos(k) : k번 operation으로 a 정렬 가능? for(int i=0; i k) return false; b[i] = p; } else { if (m - b[i] + p > n >> m; a.resize(n); for (int i = 0; i < n.. 2020. 3. 15. cf 626 div2 D - present (수론, 이분탐색) https://codeforces.com/contest/1323/problem/D 어렵지만 여기저기서 출제된 적이 있는 문제. 핵심 아이디어는 가져가자 최대 4e5개의 원소 n개를 갖는 배열이 있다. 원소는 1e7이하의 자연수를 갖는다. n개 중 2개 원소의 가능한 모든 쌍에 대해 합을 구해 모두 xor한 값을 구해라 (a1+a2)⊕(a1+a3)⊕ … ⊕(a1+an)⊕(a2+a3)⊕ … ⊕(a2+an)…⊕(an−1+an) 한 쌍의 합의 최댓값은 2e7이므로 답을 ans라 했을때 ans는 24개 비트로 표현 가능하다. ans의 k번째 비트가 켜져있는지 nlogn에 알 수 있다. a의 원소들은 k+1번 이후의 비트는 k번째 비트에 영향을 주지 않는다. b 2020. 3. 15. BOJ 15759 - Talent show (냅색, 이분탐색) https://www.acmicpc.net/problem/15759 어려움 최대 250마리의 소 n마리와 최대 1000의 무게제한W가 주어진다. 각각의 소는 최대 1e6의 무게w와 최대 1e3의 능력t가 주어진다. 소들을 적절히 골라서 무게합이 W이상인 집합 중, 능력합/무게합의 최대값을 x라고 할 때, 1000x의 소수점을 버린 값을 구하라. 고른 소들의 집합을 S라고하면 무게합은 W이상이고 다음을 만족해야 한다. 구해야 할 값은 1000x이므로 이를 y로 치환해서 다시 정리해 보면 다음과 같다. y값 1~250*1000*1000범위에 대해 이분탐색하면 된다. int pos(y) : 능력합/무게합이 y가 가능한지? dp[k] : 무게 합이 k일 때 1000T - yW의 최대값 dp[W] : 무게합이 W.. 2020. 3. 1. 이전 1 2 3 다음
