1일1알

우선 A와 B의 모든 구간에서의 누적합들을 저장하는 벡터를 만든다. A의 누적합과 B의 누적합을 더했을때 t가 되는 경우를 찾으면 되는데, 이분 탐색을 위해 둘중 하나를 정렬한다. 나는 B를 정렬했다. A의 모든 원소를 탐색하면서 B의 원소의 값이 t - A[i]인 경우를 찾으면 되는데, 이때 lower_bound와 upper_bound를 사용했다. lower_bound와 upper_bound는 이분 탐색을 해주는 함수인데, 정렬이 되어있어야 사용이 가능하다. 그래서 앞에서 B를 정렬했다. lower_bound는 찾고싶은 수보다 같거나 큰 인덱스를 반환하고 upper_bound는 찾고싶은 수보다 큰 인덱스를 반환한다. ans에 (upper_bound의 반환값 - lower_bound의 반환값) 을 더해주..

우선 입력받은 집의 위치들을 오름차순으로 정렬한다. 가능한 최소 간격은 1, 최대 간격은 제일 오른쪽 집-제일 왼쪽 집 이다. left를 1, right를 house[n-1] - house[0] 으로 놓고 이분탐색을 하면서 답을 구할 수 있다. 설치한 공유기의 수가 C보다 크거나 같으면 간격을 넓혀야 하기 때문에 left를 mid+1로 바꾼 뒤 답을 갱신해주고, 설치한 공유기의 수가 C보다 작다면 간격을 좁혀야 하기 때문에 right를 mid-1로 바꾼다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; ty..

이분 탐색으로 해결할 수 있는 문제이다. 최소를 동영상의 길이의 최소로 하고, 최대를 동영상의 길이들의 총 합으로 시작해서 이분탐색을 하면서 가장 적절한 블루레이의 크기를 구할 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m; int sum = 0; int arr[100001] = { 0 }; bool IsPossible(int value) { int cnt = 0; int sum = 0; for (int i = 0; i < n; i++) { ..