还没想好
怎样弥补荒废的青春
posts - 2,comments - 2,trackbacks - 0
有两个数组a,b,大小都为n,数组元素的值任意,无序;
要求:通过交换a,b中的元素,使数组a元素的和与数组b元素的和之间的差最小

据说要8分钟内写出代码,我试了一下,整出思路都有几分钟了,代码写出来都快个把小时了,自认为也写过那么多年的程序,也不至于那么弱爆吧,难道传说中的神人就这么厉害?
代码贴下面,高手指点:
  1 
  2 /*
  3 有两个数组a,b,大小都为n,数组元素的值任意,无序;
  4 要求:通过交换a,b中的元素,使数组a元素的和与数组b元素的和之间的差最小
  5 */
  6 
  7 /*
  8 算法思想就是先把两堆数排序,然后给结果数组分配,当一边有一个最大的数时,
  9 应该给它配一个最小的数,所以一次取两个数。当给A组分配最大MAX和最小的MIN后,
 10 再在剩下未分配的数里取出最大和最小的数分配给B,直到分完为止。
 11 这个算法并不能保证最优解,正确算法应该使用动态规划法,以后补上正解的代码。
 12 */
 13 
 14 //从剩余的数厘米找出最大的那个。
 15 //a,b分别是数组地址,offa和offb是偏移量,是值结果参数。
 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,是取最小的数。
 40 //n是数组大小。
 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     *= *b;
 69     *= t;
 70 }
 71 
 72 //主算法,输入是a,b两个数组即长度n
 73 //返回交互后两组数据和的差。
 74 //每次从两组数据里取最大和最小的组合起来,放到一边,次大和次小的放到另一边
 75 //实际上这个算法不能保证找到最优解,应该使用动态规划法来求最优解。
 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的总和大了,然后新的数又是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为奇数,剩下两个数。
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总和小,把剩下的大数给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 }


posted @ 2012-05-31 09:17 nullpointer 阅读(83) | 评论 (2)编辑 收藏
在程序员这个职业上混了十年, 最美好的青春岁月都奉献给了它,可是却没有留下多少辉煌和灿烂的记忆。十年的岁月一晃就过去,仿佛比打酱油还快,其实,这些年真的是在打酱油。。。我知道我不会继续干多久的程序了,可是一旦离开,心中还是有些不舍。一直没有写技术博客的习惯,现在就当一个空的小本子吧,看看最后会在上面记录下点什么。
posted @ 2012-03-21 14:04 nullpointer 阅读(81) | 评论 (0)编辑 收藏
仅列出标题