codeforces 620D Professor GukiZ and Two Arrays-白红宇

codeforces 620D Professor GukiZ and Two Arrays

阅读量：5266 次

发布时间：2019-06-14

本文共 5099 字，大约阅读时间需要 16 分钟。

1 #include 
     
        2   3 using namespace std;  4   5 const int maxn = 2000 + 50;  6   7 const long long inf = 1e18;  8   9 int n, m; 10  11 long long suma, sumb; 12  13 int a[maxn], b[maxn]; 14  15 long long dbl_a[maxn], dbl_b[maxn]; 16  17 long long sum_dbl_a[maxn * maxn + 10], sum_dbl_b[maxn * maxn + 10]; 18  19 int main() 20 { 21     map
      
        pos_a; 22     scanf("%d", &n); 23     for(int i = 1; i <= n; ++i){ 24         scanf("%d", &a[i]); 25         suma += a[i]; 26         dbl_a[i] = a[i] * 2; 27         pos_a[dbl_a[i]] = i; 28     } 29  30     map
       
        > m_a; 31     map
        
          two_pos_a; 32     int cnt_a = 0, cnt_b = 0; 33     for(int i = 1; i <= n; ++i){ 34         for(int j = i + 1; j <= n; ++j){ 35                 m_a[dbl_a[i] + dbl_a[j]] = make_pair(i, j); 36                 sum_dbl_a[++cnt_a] = dbl_a[i] + dbl_a[j]; 37         } 38     } 39     scanf("%d", &m); 40     for(int i = 1; i <= m; ++i){ 41         scanf("%d", &b[i]); 42         sumb += b[i]; 43         dbl_b[i] = b[i] * 2; 44     } 45  46     long long diff = (suma - sumb); 47  48     if(diff == 0) { 49         printf("0\n0\n"); 50         return 0; 51     } 52  53     sort(dbl_a+1, dbl_a+1+n); 54  55     long long one_swap_ans = abs(suma - sumb); 56     long long two_swap_ans = abs(suma - sumb); 57     int one_swap_a = 0, one_swap_b = 0; 58     int two_swap_a_1 = 0, two_swap_a_2 = 0, two_swap_b_1 = 0, two_swap_b_2 = 0; 59  60     for(int i = 1; i <= m; ++i){ 61         long long tmp = diff + dbl_b[i]; 62         int pos = lower_bound(dbl_a+1, dbl_a+n+1, tmp) - dbl_a; 63         //printf("%d\n", pos); 64         long long big_res = inf; 65         if(pos <= n) big_res = dbl_a[pos-1]; 66  67         long long small_res = inf; 68         if(pos - 1 >= 1) small_res = dbl_a[pos - 1]; 69  70         if(abs(big_res - tmp) > abs(small_res - tmp)){ 71                 //printf("%d %d %d\n",pos_a[10], dbl_a[pos-1], pos); 72                 long long temp = abs(small_res - tmp); 73                 if(one_swap_ans > temp){ 74                         one_swap_ans = temp; 75                         one_swap_a = pos_a[dbl_a[pos-1]], one_swap_b = i; 76                 } 77         } else { 78                 long long temp = abs(big_res - tmp); 79                 if(one_swap_ans > temp){ 80                         one_swap_ans = temp; 81                         one_swap_a = pos_a[dbl_a[pos]], one_swap_b = i; 82                 } 83         } 84  85     } 86  87  88  89     sort(sum_dbl_a + 1, sum_dbl_a + cnt_a + 1); 90  91  92     for(int i = 1; i <= m; ++i){ 93         for(int j = i + 1; j <= m; ++j){ 94                 long long tmp = diff + dbl_b[i] + dbl_b[j]; 95                 int pos = lower_bound(sum_dbl_a+1, sum_dbl_a+cnt_a+1, tmp) - sum_dbl_a; 96                 long long big_res = inf; 97                 if(pos <= cnt_a) big_res = sum_dbl_a[pos]; 98  99                 long long small_res = inf;100                 if(pos - 1 >= 1) small_res = sum_dbl_a[pos - 1];101 102                 if(abs(big_res - tmp) > abs(small_res - tmp)){103                         long long temp = abs(small_res - tmp);104 105                         if(two_swap_ans > temp){106                                 two_swap_ans = temp;107                                 two_swap_a_1 = m_a[sum_dbl_a[pos-1]].first;108                                 two_swap_a_2 = m_a[sum_dbl_a[pos-1]].second;109                                 two_swap_b_1 = i;110                                 two_swap_b_2 = j;111                         }112                 } else {113                         long long temp = abs(big_res - tmp);114 115                         if(two_swap_ans > temp){116                                 two_swap_ans = temp;117                                 two_swap_a_1 = m_a[sum_dbl_a[pos]].first;118                                 two_swap_a_2 = m_a[sum_dbl_a[pos]].second;119 120                                 two_swap_b_1 = i;121                                 two_swap_b_2 = j;122                         }123                 }124 125                 }126     }127 128 129         long long ans = min(abs(diff), min(abs(one_swap_ans), abs(two_swap_ans)));130         printf("%I64d\n", ans);131         if(ans == diff){132                 printf("0\n");133         } else if(one_swap_ans == ans){134                 printf("1\n");135                 printf("%d %d\n", one_swap_a, one_swap_b);136         } else {137                 printf("2\n");138                 printf("%d %d\n", two_swap_a_1, two_swap_b_1);139                 printf("%d %d\n", two_swap_a_2, two_swap_b_2);140         }141 142     return 0;143 }