import java.util.Random;
/**
* 题目:
* 给定N(1<=N<=100000)个五维的点A(x1,x2,x3,x4,x5),求两个点X(x1,x2,x3,x4,x5)和Y(y1,y2,y3,y4,y5),
* 使得他们的哈密顿距离(d=|x1-y1| + |x2-y2| + |x3-y3| + |x4-y4| + |x5-y5|)最大。|x|=abs(x)。
*
* 第一种方法当然是暴力遍历一次,求得最大值
* 第二种方法借助bitmap
* 在网上找了两个相关的资料:
* http://www.cppblog.com/sonicmisora/archive/2009/09/14/96143.aspx
* http://wenku.baidu.com/view/1e51750abb68a98271fefaa8.html
*
* 我觉得这两个资料都不好理解
* 我的理解如下:
* 1.
* 这道题目里面,使用bitmap的关键是这个:
* 先看二维的点,我们约定形如Xij下标的数字(ij)是二进制,0表示正数,1表示负数,令
* X00= x1 + x2
* X01= x1 - x2
* X10= - x1 + x2
* X11= - x1 - x2
* 用一个一维数组a保存这四个值,即a[0]=X00,a[1]=X01,a[2]=X10,a[3]=X11
* 有N个点,那么就有二维数组:A[N][S],(S=00,01,10,11)
*
* 2.(当然,更严谨的数学证明请参考上面提到的第二个链接)
* |x1-y1| = MAX(x1-y1, y1-x1);
* => |x1-y1| + |x2-y2| =
MAX{
(x1-y1)+(x2-y2)
(x1-y1)-(x2-y2)
-(x1-y1)+(x2-y2)
-(x1-y1)-(x2-y2)
};
也就是=
MAX{
(x1+x2)-(y1+y2)
(x1-x2)-(y1-y2)
(-x1+x2)-(-y1+y2)
(-x1-x2)-(-y1-y2)
};
正好是MAX{(X00-Y00), (X01-Y01), (X10-Y10), (X11-Y11)};
如果有A-Z共26个点,那么
result = MAX{
(A00-B00), (A01-B01), (A10-B10), (A11-B11),
(A00-C00), (A01-C01), (A10-C10), (A11-C11),
......
(X00-Y00), (X01-Y01), (X10-Y10), (X11-Y11),
(Y00-Z00), (Y01-Z01), (Y10-Z10), (Y11-Z11),
};
对上面的每一列应用MAX运算:
对ij=00,时,第一列有MAX(第一列)=MAX(A00,B00...Z00) - Min(A00,B00...Z00)
那么 result = MAX{MAX(第一列),MAX(第二列)...};
也就是上面提到的第一个链接里面的说法,引用一下:
A[1][0]-A[2][0]
A[1][1]-A[2][1]
A[1][2]-A[2][2]
A[1][3]-A[2][3]
然后问题就变得简单了,扫一遍,对于每个I,求出A[*][I]的最大值MAX(I)最小值MIN(I),
再用MAX(I)-MIN(I)就可以得到对于I来说的最大值了。最后取个总的最大值
* @author bylijinnan
*/
public class HamiltonDistance {
private final int N = 10 * 1000;
private final int D = 5;
private final int S = 1 << D;
public static void main(String[] args) {
HamiltonDistance h = new HamiltonDistance();
h.test();
}
public void test() {
int[][] data = sourceData();
System.out.println(maxHamiltonDistance(data));
System.out.println(maxHamiltonDistanceBitMap(data));
}
/**
* 通过枚举暴力求解
* @param data
* @return
*/
public long maxHamiltonDistance(int[][] data) {
if (data == null || data.length != N || data[0].length != D) {
System.out.println("invalid input");
return 0L;
}
long result = 0L;
for(int i = 0; i < N; i++) {
int[] pointA = data[i];
for(int j = i + 1; j < N; j++) {
int[] pointB = data[j];
long distance = distanceOfTwoPoints(pointA, pointB);
if (result < distance) {
result = distance;
}
}
}
return result;
}
//求得:|X1-Y1| + |X2-Y2| + |X3-Y3| + |X4-Y4| + |X5-Y5| + ...|Xn-Yn|
private long distanceOfTwoPoints(int[] pointA, int[] pointB) {
long result = 0L;
for(int i = 0; i < D; i++) {
result += Math.abs((long)pointA[i] - (long)pointB[i]);
}
return result;
}
/**
* 通过bitmap求解
* @param data
* @return
*/
public long maxHamiltonDistanceBitMap(int[][] data) {
//略去输入合法性检查
long result = Long.MIN_VALUE;
//求得X00000~X11111,下标是二进制
long[][] A = new long[N][S];
for (int i = 0; i < N; i++) {
for (int j = 0; j < S; j++) {
A[i][j] = getSumByBits(data[i], j);
}
}
//System.out.println(Arrays.deepToString(A));
long MAXi = Long.MIN_VALUE;
long MINi = Long.MAX_VALUE;
for (int i = 0; i < S; i++) {
for (int j = 0; j < N; j++) {
if (MAXi < A[j][i]) {
MAXi = A[j][i];
}
if (MINi > A[j][i]) {
MINi = A[j][i];
}
}
result = max(result, (MAXi - MINi));
MAXi = Long.MIN_VALUE;
MINi = Long.MAX_VALUE;
}
return result;
}
//0表示正数,1表示负数
private long getSumByBits(int[] a, int s) {
long result = 0L;
for (int i = 0; i < D; i++) {
if (exist(s, i)) {
result -= a[i];
} else {
result += a[i];
}
}
return result;
}
//value的二进制表示,在第offset位是否为1
private boolean exist(int value, int offset) {
//return (value & (1 << offset)) == 1;
return (value & (1 << offset)) != 0;
}
//生成指定维度的N个点
private int[][] sourceData() {
int[][] data = new int[N][D];
Random random = new Random();
for (int i = 0; i < N; i++) {
for (int j = 0; j < D; j++) {
int value = random.nextInt();
data[i][j] = value;
}
}
return data;
}
private long max(long x, long...yy) {
long result = x;
for(long y : yy) {
if (result < y) {
result = y;
}
}
return result;
}
}
分享到:
相关推荐
bitmap-fangsongti-fonts-0.3-15.el6.noarch.rpm是centos工具包。
----------------------------------<br>Section 1: The Basics<br> chap1-Getting Started<br> chap2-An Introduction to Unicode<br> chap3-Windows and Messages<br> chap4-An Exercise in Text Output<br> chap5...
if (bitmap.bmBitsPixel<16) //判断是否为真彩色位图 panelsize = pow(2,bitmap.bmBitsPixel*sizeof(RGBQUAD)); BITMAPINFO *pBInfo = (BITMAPINFO*)LocalAlloc(LPTR,sizeof(BITMAPINFO)+panelsize); ...
bitmap-console-fonts-0.3-15.el6.noarch.rpm是centos工具包。
离线安装包,测试可用
Converting a bitmap to a region - memory leak fix将一个位图转换成一个区域--内存泄露的修正(4KB)
离线安装包,亲测可用
bitmap-fixed-fonts-0.3-15.el6.noarch.rpm是centos工具包。
bitmapfont-for-ugui
bitmap-fonts-0.3-6.fc10.noarch.rpm
离线安装包,亲测可用
赠送jar包:RoaringBitmap-0.5.11.jar; 赠送原API文档:RoaringBitmap-0.5.11-javadoc.jar; 赠送源代码:RoaringBitmap-0.5.11-sources.jar; 赠送Maven依赖信息文件:RoaringBitmap-0.5.11.pom; 包含翻译后的API...
赠送jar包:RoaringBitmap-0.5.11.jar; 赠送原API文档:RoaringBitmap-0.5.11-javadoc.jar; 赠送源代码:RoaringBitmap-0.5.11-sources.jar; 赠送Maven依赖信息文件:RoaringBitmap-0.5.11.pom; 包含翻译后的API...
bitmap-lucida-typewriter-fonts-0.3-15.el6.noarch.rpm是centos工具包。
赠送jar包:RoaringBitmap-0.7.45.jar; 赠送原API文档:RoaringBitmap-0.7.45-javadoc.jar; 赠送源代码:RoaringBitmap-0.7.45-sources.jar; 赠送Maven依赖信息文件:RoaringBitmap-0.7.45.pom; 包含翻译后的API...
--[if lte IE 6]></td></tr></table></a><![endif]--> </li> </ul> <br class="clear" /> <ul> <li><a href="#nogo" class="four outer">SEARCH<!--[if IE 7]><!--></a><!--<![endif]--> <!--[if lte IE 6]><table>...
Converting a bitmap to a region - memory leak fix将位图转化为一个区域 - 修补了内存漏洞(179KB)
赠送jar包:RoaringBitmap-0.7.45.jar; 赠送原API文档:RoaringBitmap-0.7.45-javadoc.jar; 赠送源代码:RoaringBitmap-0.7.45-sources.jar; 赠送Maven依赖信息文件:RoaringBitmap-0.7.45.pom; 包含翻译后的API...
swftools linux编译 【资源】gbsn00lp.ttf gkai00mp.ttf xpdf-chinese-simplified.tar....bitMapc=-T 9 -s poly2bitmap -s zoom=150 zoom=150 langc=-s languagedir=/usr/local/xpdf-chinese-simplified port = 8100
1.把24位BMP变灰度图像 2.进行直方图均衡化,提高图像对比度 3.进行均值滤波 第二个均衡化做了N天。。。每天回寝室看一眼以为是算法错了。。后来终于发现是一个溢出的小错误,duang。。这都是假的。。是特技的溢出。...