题目描述
一张n*m的地图，每个格子里面有一定数量的神奇宝贝，求一个最优位置，使得所有神奇宝贝到该位置的曼哈顿距离最小。
一共有T组数据，每组数据包含两行，第一行是n和m(1<=n,m<=2000)，第二行是三个整数x,y,q，表示处于（i，j）(1<=i<=n,1<=j<=m)的神奇宝贝的数量为((x^i) + (y^j))mod q，其中1<=x,y<=2000，1<=q<=10。
输出最小的曼哈顿距离和。
解题思路
这道题与2015编程之美挑战赛的基站选址类似（其实可以说是简单版），当时我没有做出来，给个地址吧：http://hihocoder.com/problemset/problem/1150
分析题目可以发现，由于是求曼哈顿距离，所以横行和竖行可以分开考虑，于是问题就变成了求加权平均数的问题。
公式：ans_x = ∑(ai*i) / ∑ai，ans_y = ∑(bj*j) / ∑bj，其中ai表示第i行的神奇宝贝数量，bi表示第i列的神奇宝贝数量，当然有∑ai == ∑bj。
这里有两点需要注意：
1、当结果不是整数时，涉及到向上取整还是向下取整的问题，由于与所有非零点的分布有关，所以最简单的办法是有可能成为答案的四个点都做一次判断就好了。
2、这里涉及到除法，所以可能会出现分母为零的情况，即地图上木有神奇宝贝【o(≧口≦)o摔桌子】，所以要特判…… 我才不会说我因为这个wa了好久QAQ
附：c++代码
（代码中有被注释掉的高精度的部分，因为我之前对数据规模的估计出错了…… 目前的高精度的代码还有错误，所以借鉴需要注意……）
时间复杂度O(n^2)
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 5 using namespace std; 6 #define MaxN 2020 7 #define MLen 14 8 9 typedef int hp[MLen]; 10 typedef long long llt; 11 12 llt H[MaxN], L[MaxN]; 13 int n, m; 14 15 inline void Add(hp a, hp b, hp &Ret) 16 { 17 int i, Len = max(a[0], b[0]) + 1; 18 hp c; 19 for(i = 1; i <= Len; i++) 20 c[i] = 0; 21 for(i = 1; i <= Len; i++) 22 { 23 c[i] += a[i] + b[i]; 24 c[i + 1] += c[i] / 10; 25 c[i] %= 10; 26 } 27 while(Len > 1 && c[Len] == 0) 28 Len--; 29 c[0] = Len; 30 for(i = 0; i <= Len; i++) 31 Ret[i] = c[i]; 32 } 33 34 inline void Add_Num(hp a, int b, hp &Ret) 35 { 36 int i, Len = a[0] + 1; 37 hp c; 38 for(i = 1; i <= Len - 1; i++) 39 c[i] = a[i]; 40 c[i] = 0; 41 c[1] += b; 42 for(i = 1; i <= Len; i++) 43 { 44 c[i + 1] += c[i] / 10; 45 c[i] %= 10; 46 } 47 while(Len > 1 && c[Len] == 0) 48 Len--; 49 c[0] = Len; 50 for(i = 0; i <= Len; i++) 51 Ret[i] = c[i]; 52 } 53 54 inline void Mul_Num(hp a, int b, hp &Ret) 55 { 56 int i, Len = a[0] + 5; 57 hp c; 58 for(i = 1; i <= a[0]; i++) 59 c[i] = a[i] * b; 60 for(i = a[0] + 1; i <= Len; i++) 61 c[i] = 0; 62 for(i = 1; i <= Len; i++) 63 { 64 c[i + 1] += c[i] / 10; 65 c[i] %= 10; 66 } 67 while(Len > 1 && c[Len] == 0) 68 Len--; 69 c[0] = Len; 70 for(i = 0; i <= Len; i++) 71 Ret[i] = c[i]; 72 } 73 74 inline bool Check(hp a, hp b) // a<b 75 { 76 if(a[0] < b[0]) 77 return true; 78 if(a[0] > b[0]) 79 return false; 80 for(int i = a[0]; i >= 1; i--) 81 if(a[i] < b[i]) 82 return true; 83 else if(a[i] > b[i]) 84 return false; 85 return true; 86 } 87 88 inline int Chu(hp a, hp b) // a/b 89 { 90 int Low = 0, High = 2020, Mid; 91 hp tmp; 92 int op; 93 while(Low < High) //[,) 94 { 95 Mid = Low + (High - Low) / 2; 96 Mul_Num(b, Mid, tmp); 97 if(Check(tmp, a)) //tmp < a 98 { 99 Low = Mid + 1; 100 op = 0; 101 } 102 else 103 { 104 High = Mid; 105 op = 1; 106 } 107 } 108 if(!op) 109 return Low - 1; 110 else 111 return High - 1; 112 } 113 114 inline void Cal_Dis(int ph, int pl, llt &Ret) 115 { 116 int i, j; 117 //hp Ans; 118 llt Ans = 0; 119 //Ans[0] = 1; Ans[1] = 0; 120 for(i = 1; i < ph; i++) 121 //Add_Num(Ans, (ph - i) * H[i], Ans); 122 Ans += (llt)(ph - i) * H[i]; 123 for(i = ph + 1; i <= n; i++) 124 //Add_Num(Ans, (i - ph) * H[i], Ans); 125 Ans += (llt)(i - ph) * H[i]; 126 for(j = 1; j < pl; j++) 127 //Add_Num(Ans, (pl - j) * L[j], Ans); 128 Ans += (llt)(pl - j) * L[j]; 129 for(j = pl + 1; j <= m; j++) 130 //Add_Num(Ans, (j - pl) * L[j], Ans); 131 Ans += (llt)(j - pl) * L[j]; 132 //for(i = 0; i <= Ans[0]; i++) 133 // Ret[i] = Ans[i]; 134 Ret = Ans; 135 } 136 137 inline void Print(hp a) 138 { 139 for(int i = a[0]; i >= 1; i--) 140 printf("%d", a[i]); 141 printf("\n"); 142 } 143 144 int main() 145 { 146 int T; 147 int x, y, q; 148 int i, j, Num; 149 llt Ans, tmp; 150 //hp Sum_h, Sum_l, Psum_h, Psum_l; 151 llt Sum_h, Sum_l, Psum_h, Psum_l; 152 double ph, pl; 153 scanf("%d", &T); 154 while(T--) 155 { 156 scanf("%d%d", &n, &m); 157 scanf("%d%d%d", &x, &y, &q); 158 Psum_h = Psum_l = Sum_h = Sum_l = 0; 159 //Psum_h[0] = Psum_l[0] = Sum_h[0] = Sum_l[0] = 1; 160 //Psum_h[1] = Psum_l[1] = Sum_h[1] = Sum_l[1] = 0; 161 for(j = 1; j <= m; j++) 162 L[j] = 0; 163 for(i = 1; i <= n; i++) 164 { 165 H[i] = 0; 166 for(j = 1; j <= m; j++) 167 { 168 Num = ((x ^ i) + (y ^ j)) % q; 169 H[i] += Num; 170 L[j] += Num; 171 } 172 Sum_h += H[i]; 173 Psum_h += (llt)i * H[i]; 174 //Add_Num(Sum_h, H[i], Sum_h); 175 //Add_Num(Psum_h, i * H[i], Psum_h); 176 } 177 for(j = 1; j <= m; j++) 178 { 179 Sum_l += L[j]; 180 Psum_l += (llt)j * L[j]; 181 //Add_Num(Sum_l, L[j], Sum_l); 182 //Add_Num(Psum_l, j * L[j], Psum_l); 183 } 184 //ph = Chu(Psum_h, Sum_h); 185 //pl = Chu(Psum_l, Sum_l); 186 if(!Sum_h) //Sum_h == Sum_l 187 { 188 printf("0\n"); 189 continue; 190 } 191 ph = Psum_h / Sum_h; 192 pl = Psum_l / Sum_l; 193 Cal_Dis(ph, pl, Ans); 194 Cal_Dis(ph + 1, pl, tmp); 195 //if(Check(tmp, Ans)) 196 //for(i = 0; i <= tmp[0]; i++) 197 // Ans[i] = tmp[i]; 198 if(tmp < Ans) 199 Ans = tmp; 200 Cal_Dis(ph, pl + 1, tmp); 201 //if(Check(tmp, Ans)) 202 //for(i = 0; i <= tmp[0]; i++) 203 // Ans[i] = tmp[i]; 204 if(tmp < Ans) 205 Ans = tmp; 206 Cal_Dis(ph + 1, pl + 1, tmp); 207 //if(Check(tmp, Ans)) 208 //for(i = 0; i <= tmp[0]; i++) 209 // Ans[i] = tmp[i]; 210 if(tmp < Ans) 211 Ans = tmp; 212 printf("%lld\n", Ans); 213 //Print(Ans); 214 } 215 return 0; 216 }
另一种思路
这是官方给的题解，没太明白O(n)是怎样实现的。
题目链接：https://biancheng.love/contest-ng/index.html#/29/problems
原文：http://www.cnblogs.com/CQBZOIer-zyy/p/5049568.html
