반례좀 알려주시면 안될까요
Chaiho Reply 8 years 24 weeks ago
제가 처음 풀다가 실패한 방법인데 다른방법으로 풀긴했는데 이게 어떤 반례가 있는지 궁금하네요 ㅠㅠ
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner input= new Scanner(System.in);
int a= input.nextInt();
int b= input.nextInt();
int midA=0;
int midB=0;
int lowB=0,lowA=0;
int highB=b-1,highA=a-1;
int Ans=0;
double N= input.nextDouble();
int A[]= new int[a];
int B[]= new int[b];
for(int i=0;i<a;i++){
A[i]=input.nextInt();
}
for(int i=0;i<b;i++){
B[i]=input.nextInt();
}
midA=a/2;
midB=b/2;
int diff=(int)Math.abs(A[midA]+B[midB]-N);
while(true){
while(true){
if(midB-1>=0&&diff>Math.abs(A[midA]+B[midB-1]-N)){
diff=(int)Math.abs(A[midA]+B[midB-1]-N);
highB=midB-1;
midB=(lowB+highB)/2;
if(lowB==highB-1) {
if(diff>Math.abs(A[midA]+B[lowB]-N)){
diff=(int)Math.abs(A[midA]+B[lowB]-N);
}
else if(diff>Math.abs(A[midA]+B[highB]-N)){
diff=(int)Math.abs(A[midA]+B[highB]-N);
}
}
}
else if(midB+1<b&&diff>Math.abs(A[midA]+B[midB+1]-N)){
diff=(int)Math.abs(A[midA]+B[midB+1]-N);
lowB=midB+1;
midB=(lowB+highB)/2;
if(lowB==highB-1) {
if(diff>Math.abs(A[midA]+B[lowB]-N)){
diff=(int)Math.abs(A[midA]+B[lowB]-N);
}
else if(diff>Math.abs(A[midA]+B[highB]-N)){
diff=(int)Math.abs(A[midA]+B[highB]-N);
}
}
}
else{
break;
}
}
if(midA-1>=0&&diff>Math.abs(A[midA-1]+B[midB]-N)){
diff=(int)Math.abs(A[midA-1]+B[midB]-N);
highA=midA-1;
midA=(lowA+highA)/2;
if(lowA==highA-1) {
if(diff>Math.abs(A[lowA]+B[midB]-N)){
diff=(int)Math.abs(A[lowA]+B[midB]-N);
}
else if(diff>Math.abs(A[highA]+B[midB]-N)){
diff=(int)Math.abs(A[highA]+B[midB]-N);
}
}
}
else if(midA+1<a&&diff>Math.abs(A[midA+1]+B[midB]-N)){
diff=(int)Math.abs(A[midA+1]+B[midB]-N);
lowA=midA+1;
midA=(lowA+highA)/2;
if(lowA==highA-1) {
if(diff>Math.abs(A[lowA]+B[midB]-N)){
diff=(int)Math.abs(A[lowA]+B[midB]-N);
}
else if(diff>Math.abs(A[highA]+B[midB]-N)){
diff=(int)Math.abs(A[highA]+B[midB]-N);
}
}
}
else{
break;
}
}
System.out.print(diff);
}
}
pichulia 
Reply 8 years 24 weeks ago
Reply 8 years 24 weeks ago
3 3 10
1 5 9
1 6 9
이런 데이터가 있겠네요.
지금 midA = 5 부터 시작해서 x랑 차이가 가장 작은 midB 6을 "고정"시켜놓고,
그 다음에 midB = 6 이랑 x랑 차이가 가장 작은 midA를 찾고있네요.
이렇게 하면 1 + 9 = 10 을 찾지 못하게 됩니다.
Chaiho Reply 8 years 23 weeks ago
아! 감사합니다!!