알고리즘225 구간 만들기 자주나오니까 복붙하지말고 따라서 타이핑 0또는 1로 이뤄진 불린타입 배열 a에서 1 구간을 vector a에 {시작점, 끝점} 끝점으로 넣는 코드 int lo = -1, hi = -1; for (int i = 0; i 0 && a[i - 1] == 0)) lo = hi = i; else hi++; if (i == n - 1) ap.push_back({ lo,hi }); } else if (a[i - 1] == 1) ap.push_back({ lo,hi }); } 2020. 3. 9. 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. BOJ 15758 - Milking order (이분탐색, 위상정렬) https://www.acmicpc.net/problem/15758 최대 5만개의 법칙 M개가 주어진다. 법칙마다 순서가 주어진다. 예를들어 1 4 3이면 최종 결과에 1 4 3 이 순서대로 나타나야 한다. 앞에서부터 최대한 많은 법칙을 사용해서 유효한 n의 permutation을 만들고자 할 때, n의 permutation을 구하라. 앞에서부터 법칙 1개 ~ m개를 만족할 때에 대해 가능한지 이분탐색한다. bool pos(int k) 함수에서 앞에서부터 k개의 법칙을 이용해서 위상정렬 가능한지 반환하면 된다. 단, 가능한 수열 중 사전 순으로 가장 앞선 수열을 출력해야하므로 위상정렬시 pq를 쓰면 된다. int n, m, ind[MAX]; vector odr[50004]; vector topo; vec.. 2020. 3. 1. BOJ 15745 - Snow boots (오프라인 쿼리, 유니온 파인드) https://www.acmicpc.net/problem/15745 최대 1e5개의 음이 아닌 정수 n개가 주어진다. 첫번째와 마지막은 0임이 보장된다. 쿼리 s d가 최대 1e5개 주어진다. 배열에서 s를 초과하는 연속하는 부분수열의 최대 길이 < d인 경우 1을, 그 외엔 0을 출력한다. s에 대해 내림차순으로 query를 정렬한다. 각 쿼리마다 배열에서 서로 인접하면서 s를 초과하는 값을 갖는 인덱스끼리 merge해준다. (한 번 처리한 값을 중복해서 처리하지 않도록 한다) 그러면 각 쿼리마다 집합들 중 최대 크기가 s를 초과하는 연속하는 부분 수열의 길이가 된다. 쿼리마다 O(lgN)에 최대값을 찾고 모든 쿼리에 걸쳐 인덱스에 대해 한번씩만 연산하므로 O(QlgN+N)쯤 될 것 같다. int n,.. 2020. 3. 1. 이전 1 ··· 11 12 13 14 15 16 17 ··· 57 다음
