有兩個數(shù)組a,b，大小都為n,數(shù)組元素的值任意，無序；
要求：通過交換a,b中的元素，使數(shù)組a元素的和與數(shù)組b元素的和之間的差最小
據(jù)說要8分鐘內(nèi)寫出代碼，我試了一下，整出思路都有幾分鐘了，代碼寫出來都快個把小時(shí)了，自認(rèn)為也寫過那么多年的程序，也不至于那么弱爆吧，難道傳說中的神人就這么厲害？
代碼貼下面，高手指點(diǎn)：
1
2 /*
3 有兩個數(shù)組a,b，大小都為n,數(shù)組元素的值任意，無序；
4 要求：通過交換a,b中的元素，使數(shù)組a元素的和與數(shù)組b元素的和之間的差最小
5 */
6
7 /*
8 算法思想就是先把兩堆數(shù)排序，然后給結(jié)果數(shù)組分配，當(dāng)一邊有一個最大的數(shù)時(shí)，
9 應(yīng)該給它配一個最小的數(shù)，所以一次取兩個數(shù)。當(dāng)給A組分配最大MAX和最小的MIN后，
10 再在剩下未分配的數(shù)里取出最大和最小的數(shù)分配給B，直到分完為止。
11 這個算法并不能保證最優(yōu)解，正確算法應(yīng)該使用動態(tài)規(guī)劃法，以后補(bǔ)上正解的代碼。
12 */
13
14 //從剩余的數(shù)厘米找出最大的那個。
15 //a,b分別是數(shù)組地址，offa和offb是偏移量，是值結(jié)果參數(shù)。
16 int get_max(int *a, int *offa, int *b, int *offb)
17 {
18 if(*offa == 0)
19 {
20 (*offb)--;
21 return b[*offb+1];
22 }
23 else if(*offb == 0)
24 {
25 (*offa)--;
26 return a[*offa+1];
27 }
28
29 if(a[*offa] > b[*offb])
30 {
31 (*offa)--;
32 return a[*offa+1];
33 }else{
34 (*offb)--;
35 return b[*offb+1];
36 }
37 }
38
39 //類似get_max,是取最小的數(shù)。
40 //n是數(shù)組大小。
41 int get_min(int *a, int *offa, int *b, int *offb, int n)
42 {
43 if(*offa == n)
44 {
45 (*offb)++;
46 return a[*offb-1];
47 }
48 else if(*offb == n)
49 {
50 (*offa)++;
51 return a[*offa-1];
52 }
53
54 if(a[*offa] < b[*offb])
55 {
56 (*offa)++;
57 return a[*offa-1];
58 }else{
59 (*offb)++;
60 return a[*offb-1];
61 }
62 }
63
64 //這個就不解釋了吧
65 void swap_i(int *a, int *b)
66 {
67 int t = *a;
68 *a = *b;
69 *b = t;
70 }
71
72 //主算法，輸入是a，b兩個數(shù)組即長度n
73 //返回交互后兩組數(shù)據(jù)和的差。
74 //每次從兩組數(shù)據(jù)里取最大和最小的組合起來，放到一邊，次大和次小的放到另一邊
75 //實(shí)際上這個算法不能保證找到最優(yōu)解，應(yīng)該使用動態(tài)規(guī)劃法來求最優(yōu)解。
76 int swap_x(int *a, int *b, int n)
77 {
78 int sa, sb, la, lb, *na, *nb, idx, delta, d;
79 na = new int[n];
80 nb = new int[n];
81 idx = 0;
82 delta = 0;
83 sa = sb = 0;
84 la = lb = n - 1;
85
86 sort(a, a+n);
87 sort(b, b+n);
88
89 while(idx < n-1)
90 {
91 //先給A和B一邊分配一個最大的
92 na[idx] = get_max(a, &la, b, &lb);
93 nb[idx] = get_max(a, &la, b, &lb);
94 d = na[idx] - nb[idx];
95 idx++;
96 //然后一邊分配一個最小的
97 na[idx] = get_min(a, &la, b, &lb, n);
98 nb[idx] = get_min(a, &la, b, &lb, n);
99 d += na[idx] - nb[idx];
100 idx++;
101
102 if(delta > 0 && d > 0)
103 { //A這邊總和比B的總和大了，然后新的數(shù)又是A這邊大，則需要交換
104 swap_i(na+idx, nb+idx);
105 swap_i(na+idx-1, nb+idx-1);
106 d = -d;
107 }
108 delta += d;
109 }
110
111 //n為奇數(shù)，剩下兩個數(shù)。
112 if(idx == n-1)
113 {
114 if(delta > 0)
115 { //A總和大，把剩下最后一個小的給A
116 na[idx] = get_min(a, &la, b, &lb, n);
117 nb[idx] = get_max(a, &la, b, &lb);
118 }else{ //A總和小，把剩下的大數(shù)給A
119 na[idx] = get_max(a, &la, b, &lb);
120 nb[idx] = get_min(a, &la, b, &lb, n);
121 }
122 }
123
124 memcpy(a, na, n*sizeof(a[0]);
125 memcpy(b, nb, n*sizeof(b[0]);
126 delete [] na;
127 delete [] nb;
128 return delta;
129 }
|