AcWing 1855. 愤怒的奶牛-------------------------------------------------贪心+双指针√
原题链接
中等
作者:
古德古德
,
2022-03-31 22:44:13
,
所有人可见
,
阅读 137
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 110, INF = 1e9;
int p[N];
int main()
{
cin >> n;
p[0] = -INF , p[n+1] = INF;
for(int i = 1 ; i <= n ; i++) cin >> p[i];
sort(p+1,p+n+1);
int res = 0;
for(int i = 1; i <= n ; i++)
{
int R1 = 1, pos1 = i;
while(p[pos1] - p[pos1-1] <= R1) //如果还能接着往左拓展
{
int k = pos1;
while(p[pos1] - p[k-1] <= R1) k --;
pos1 = k;
R1 ++;
}
int R2 = 1, pos2 = i;
while(p[pos2+1]-p[pos2] <= R2)
{
int k = pos2;
while(p[k+1] - p[pos2] <= R2) k ++;
pos2 = k;
R2 ++;
}
res = max(res, pos2-pos1+1);
}
cout << res;
return 0;
}