AcWing 4423. $\color{red}{最近距离}$
原题链接
中等
作者:
Finn2009
,
2022-05-21 21:02:07
,
所有人可见
,
阅读 851
首先得想到这个(这个会超时),有脑子就能想到
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000;
int a[maxn];
int main() {
int n, x, y;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++) {
if (a[i] == 0)
cout << "0 ";
else {
x = i, y = i;
while (1) {
x--, y++;
if (a[x] == 0 and x >= 1) {
cout << i - x << " ";
break;
}
if (a[y] == 0 and y <= n) {
cout << y - i << " ";
break;
}
}
}
}
return 0;
}
不过有更简洁的…据@[省选加油] 说,这是哈希表
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000000;
int a[maxn], p[maxn];
int main() {
int n, m = 0, p1 = 1;//p1记录是第几个零
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
if (a[i] == 0){
m++;
p[m] = i;
//日常记录位置
}
}
for (int i = 1; i <= n; i++){
if (a[i] == 0){
cout << "0 ";
if (a[i + 1] == 0) p1++;//如果连续两个零,p1++
}
else{
if (min(abs(i - p[p1]), abs(p[p1 + 1] - i)) == p[p1 + 1] - i) p1++;//这句话一定要看懂!
//比较i更接近哪个零
if (p1 > m) p1--;
//别超范围了~
cout << abs(i - p[p1]) << " ";
}
}
return 0;
}
clean
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000000;
int a[maxn], p[maxn];
int main() {
int n, m = 0, p1 = 1;
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
if (a[i] == 0){
m++;
p[m] = i;
}
}
for (int i = 1; i <= n; i++){
if (a[i] == 0){
cout << "0 ";
if (a[i + 1] == 0) p1++;
}
else{
if (min(abs(i - p[p1]), abs(p[p1 + 1] - i)) == p[p1 + 1] - i) p1++;
if (p1 > m) p1--;
cout << abs(i - p[p1]) << " ";
}
}
return 0;
}
### 题解的正确写法
有脑子的都知道那个会超时,还写两个这不是搞人心态吗
第二个AC了呀,不超时;第一个超时,那个是双指针
双指针是不是O(n)时间复杂度,最后是不是也是O(n^2)时间复杂度
我写了双指针超时,正确代码是第二个,有问题么
这就是防止没脑子的人直接抄代码hh