51nod3143
Description
n位战士即将奔赴战场，他们每个人都有一个攻击值ai和一个防御值bi，现在你想设计一种装备给这n位战士，如果这件装备的攻击值为A，防御值为B，那么对于第i位战士这件装备的不匹配度为$max(|A−a_i|,|B−b_i|)$
A，B都是正整数，要让所有战士的不匹配度之和最小，求出最小的不匹配度之和$2\le N \le 100000$
Solution
题意中很明显是切比雪夫距离，可以将其转换为曼哈顿距离
对于点$(x,y)$,转换为$(\frac{x+y}{2},\frac{x-y}{2})$
然后可以求出转换后横坐标和纵坐标的中位数，再以这个中位数为基准，将四周3*3的范围内的点都进行计算，去最小值。
由于涉及除法，可能会发生精度丢失，可以将所有坐标都扩大二倍，最后让答案除以2
同时要注意，这里的A，B都是整数，也就是说我们进行计算的点必须也是整数点，可以通过奇偶关系来判断。答案只用A，B为整数点转换过来的点进行计算。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include<iostream>
#include<cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define debug cout<<0<<endl
#define ll long long
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
using namespace std;
struct point
{
ll a, b;
} arr[MAXN];
int dx[] = {0, 1, -1, 0, 0, 1, 1, -1, -1};
int dy[] = {0, 0, 0, 1, -1, 1, -1, 1, -1};
ll x[MAXN];
ll y[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
int xx, yy;
for (int i = 1; i <= N; i++) {
cin >> xx >> yy;
x[i] = arr[i].a = (xx + yy);
y[i] = arr[i].b = (xx - yy);
}
sort(x+1,x+N+1);
sort(y+1,y+N+1);
int A, B;
ll ans = __LONG_LONG_MAX__;
if (N&1) {
A = x[N/2+1];
B = y[N/2+1];
} else {
A = x[N/2+1];
B = y[N/2+1];
}
ll ans2 = 0;
for (int i = 0; i <= 8; i++) {
int tx = A + dx[i];
int ty = B + dy[i];
if ((tx-ty)%2==1 || ((tx+ty))%2==1) continue;
ll temp = 0;
for (int j = 1; j <= N; j++) {
temp += abs(arr[j].a-tx) + abs(arr[j].b-ty);
}
ans = min(ans, temp);
}
cout << ans/2;
return 0;
}
|
Zhiwei Zhang
included in Algorithm