- k<10억
- 제일 큰 수에 1이 있으면?
- 제일 큰 수에 1이 없으면?
- 1이 붙은 수 중 가장 큰 수를 늘리거나
- 중간값을 늘리거나
- 효율 갈수록 안좋아짐
- 이거 이분탐색 되려나?
- 효율 이김/안이김 이분탐색?
- 몰빵보다 좋음/안좋음?
- 이건 몰빵한테 따이는 시점 이분탐색인데
- 중간값을 늘리는 시도를 점차 증가시켜본다?
- 왜 그게 그렇게 되지?
- 왜 최대 원소가 효율을 뽑기 시작하거나
- k 개 중 x개를 투자하면
- 그 이후 k - x 개는 무조건 큰 수에 넣는게 제일 고효율이다
- 문턱값을 넘으면 그 이후는 거기에 몰빵하는게 무조건 이득
- 중간값을 올리는데 전부 몰빵하거나
- 문턱값 안넘을거면 그냥 중간값 올리는데 몰빵이 나음
- 그럼 중간값을 어떻게 올리지?
- 순서가 동적으로 바뀌는데
- 정해진 기준이 있나?
- n번 돌면서 확인
- 그래놓고 중간값이 그거 넘나 확인
- 횟수는 가능한가 확인
- 이분탐색은 어떻게 하지?
- 중간값 기준?
- 합 기준?
- 합 기준으로 수행하는게 훨씬 깔끔하다.
- 목표값(합) - 최댓값 을 중간값의 목표로 잡는다.
import java.io.*;
import java.util.*;
import java.util.function.Function;
//Change Class Name to Problem Name
public class C_1998 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int test = Integer.parseInt(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < test; i++) {
run(br, bw);
}
bw.flush();
}
public static void run(BufferedReader br, BufferedWriter bw) throws IOException{
String line = br.readLine();
StringTokenizer st = new StringTokenizer(line);
int n;
long k;
n = Integer.parseInt(st.nextToken());
k = Long.parseLong(st.nextToken());
List<Point> arr = new ArrayList<>();
String aLine = br.readLine();
String bLine = br.readLine();
StringTokenizer aTokens = new StringTokenizer(aLine);
StringTokenizer bTokens = new StringTokenizer(bLine);
for (int i = 0; i < n; i++) {
long a = Long.parseLong(aTokens.nextToken());
long b = Long.parseLong(bTokens.nextToken());
arr.add(new Point(a, b));
}
Collections.sort(arr);
long max = 0;
for (int i = 0; i < n; i++) {
long now = arr.get(i).a;
if(arr.get(i).b == 1) now += k;
if(i < n / 2) now += arr.get(n/2).a;
else now += arr.get((n - 2)/2).a;
if(now > max) max = now;
}
long left = 0L;
long right = 3_000_000_100L;
Function<Long, Boolean> check = val -> {
long cnt = 0;
long aim = (val + 1) / 2;
if(arr.get(n-1).a > val / 2) aim = val - arr.get(n-1).a;
long cost = 0;
for(int i = n-1; i>= 0; i--){
if(arr.get(i).a >= aim){
cnt++;
}
else if(arr.get(i).b==1){
cnt++;
cost += aim - arr.get(i).a;
}
if(cnt == (n + 1) / 2 + 1) break;
}
if(cnt < (n + 1)/2 + 1) return false;
else if (cost > k) return false;
return true;
};
while(left <= right){
long mid = (left + right)/2;
if(check.apply(mid)){
left = mid + 1;
}else{
right = mid - 1;
}
}
bw.write(String.valueOf(Math.max(max, right)));
bw.write('\n');
}
static class Point implements Comparable<Point>{
long a;
long b;
public Point(long a, long b) {
this.a = a;
this.b = b;
}
@Override
public int compareTo(C_1998.Point o) {
if(this.a < o.a){
return -1;
}
if(this.a > o.a){
return 1;
}
if(this.a == o.a){
if(this.b < o.b){
return 1;
}
if(this.b > o.b){
return -1;
}
}
return 0;
}
}
}
/*
찾아야 할 것들
1. int 오버플로우, out of bounds
2. 특수한 경우(n=1?)
3. 잘못된 가정 & 증명
*아무것도 하지 않는 대신 무언가를 수행하기. 체계적인 상태를 유지.
*적어두기 & 구하고자 하는 것의 계층 구조 표현 -> 정확히 & 입체적으로 파악
*한가지 접근 방식에 얽메이지 말기 -> 응용의 끝 알기
*/
// 알고리즘의 작동방식 "완전히" 이해하려 노력하기
// 수행 목표
// 1. 아이디어 획득 : "추론"
// - 문제 알고리즘/특징의 "증명"으로 아이디어
// - {BruteForce, greedy, D&C, DP, graph, math}
// - 전체 알고리즘이 “결국 구하고자 하는 것” 놓치지 않기
// - “책임” 뽑아내기
// - 각 기능들이 어떤 책임을 가지고 있는지
// - “어떤 패턴”으로 동작하는지
// - 가장 Naive한 상태/알고리즘부터 시작하기 (완전 탐색, 단순 자료구조)
// - 뚜렷한 증명이 나오지 않을 땐, 어떤 기준을 만들고 나눠서 보기
// - 단위 동작의 조건 분기 파악
// - 가장 극단적인 경우에서 추론 (가장 차이가 뚜렷한 예제)
// 2. "처음"부터 직접 경우의 수 전개(수식&도식화, 엄밀한 조건 정리)
// - 알고리즘 내에 어떤 역할들이 있는지 -> 직접 들어가보기
// - 알고리즘 내에 어떤 기능들이 있는지 -> 직접 수행해보기
// 3. cutting | 구현(차근차근 단순화 & 최적화)
/*
take notes.
// 다시 보는용이 아닌
// 현재의 흐름을 가장 잘 이어갈 수 있도록 !!!
*/
// commit 시 피드백할 것 Message로 남겨두기!!
// 틀리면 느낌표 추가하기