cf 1004 D. Sonya and Matrix
題意
給你t個數字,要組成一個\(n*m\)的矩陣,這個矩陣裡面的元素等于該點到數字0的曼哈頓距離,問是否能構造出這樣的一個矩陣,如果可以,輸出數字0所在的左邊以及n和m。不能就輸出-1.
題解
第一次接觸曼哈頓距離
可以知道,最大值maxn肯定是位于某一個角上,我們假設是(n, m);
假設中心點為(x, y),那麼式子maxn = n - x + m - y;
假設元素i的數量少于\(i * 4\) 那麼說明有元素i位于了邊界外,就是x = i
然後枚舉每一個n和m,求出y。(n和m肯定是t的因子
複雜度具高,居然能過
#include <cstdio>
#include <algorithm>
int c[1000010], cnt[1000010];
int t, x, y, maxn = 0;
int main() {
scanf("%d", &t);
for(int i = 1; i <= t; i++) {
scanf("%d", &x);
c[x]++;
if(maxn < x) maxn = x;
}
x = 0;
for(int i = 1; i <= t; i++) {
if(c[i] != 4 * i) {
x = i;
break;
}
}
for(int i = 1; i <= t; i++) {
if(t % i == 0) {
int n = i, m = t / i;
y = n + m - x - maxn;
if(abs(n - x) + abs(m - y) != maxn) continue;
for(int j = 0; j <= n + m; j++) cnt[j] = 0;
for(int j = 1; j <= n; j++) {
for(int k = 1; k <= m; k++) {
cnt[abs(x - j) + abs(y - k)]++;
}
}
int flag = 0;
for(int j = 0; j <= maxn; j++) {
if(cnt[j] != c[j]) {
flag = 1;
break;
}
}
if(flag == 0) {
printf("%d %d\n%d %d\n", n, m, x, y);
return 0;
}
}
}
printf("-1\n");
return 0;
}
轉載于:https://www.cnblogs.com/fanshhh/p/11371015.html