BOJ 4373 - 수집합

BOJ 4373 - 수집합

$a+b=d-c$ 를 찾는 문제이고 set,map 떡칠 자료구조로 어떻게 잘 중복을 해결해서 세거나 투 포인터로 해결할 수 있다.

$(a,b)$ 쌍, $(c,d)$쌍 $O(n^2)$ 개를 만들어두자.

이걸 $(a+b)$와 $(d-c)$크기순으로 정렬하고 투 포인터를 진행하자.

$a+b=d-c$ 인 경우 $d$와 $c$가 $a$나 $b$와 중복되었는지 체크하고 그렇다면 다음 $(c,d)$ 쌍으로 넘어간다.

그런데 $d-c$ 로 정렬한 것 말고 $c-d$ 로 정렬한 것도 동일하게 두 번 봐줘야한다.

구현이 매우 까다롭다.

void solve() {  
   while (1) {  
      int n;  
      cin >> n;  
      if (!n) break;  
      vi arr(n);  
      fv(arr);  
      vector<array<int, 3>> ab, cd;  
      for (int a = 0; a < n; a++)  
         for (int b = a + 1; b < n; b++) {  
            ab.pb({arr[a] + arr[b], arr[a], arr[b]});  
            cd.pb({arr[b] - arr[a], arr[a], arr[b]});  
         }  
      sort(all(ab));  
      sort(all(cd));  
      int N = sz(ab);  
  
      int ans = INT_MIN;  
      for (int l = 0, r1 = 0, r2 = N - 1; l < N; l++) {  
         while (r1 < N && ab[l][0] > cd[r1][0])r1++;  
         while (r2 >= 0 && ab[l][0] > -cd[r2][0])r2--;  
         if (r1 < N && cd[r1][0] == ab[l][0]) {  
            int cr = r1;  
            while (cr < N && cd[cr][0] == cd[r1][0])cr++;  
  
            for (int R = r1; R < cr; R++) {  
               if (cd[R][1] == ab[l][1] || cd[R][1] == ab[l][2] || cd[R][2] == ab[l][1] || cd[R][2] == ab[l][2])  
                  continue;  
               maxa(ans, cd[R][2]);  
            }  
         }  
         if (r2 >= 0 && -cd[r2][0] == ab[l][0]) {  
            int cr = r2;  
            while (cr >= 0 && cd[cr][0] == cd[r2][0])cr--;  
  
            for (int R = cr + 1; R <= r2; R++) {  
               if (cd[R][1] == ab[l][1] || cd[R][1] == ab[l][2] || cd[R][2] == ab[l][1] || cd[R][2] == ab[l][2])  
                  continue;  
               maxa(ans, cd[R][1]);  
            }  
         }  
      }  
      cout << (ans == INT_MIN ? "no solution" : to_string(ans)) << endl;  
   }  
}