从原点开始,我们要枚举所有能扩展m
次的情况。
如果先向左扩展了i
次,那么向右的次数就剩下了m - 2i
次(如果这个值大于0)。先向右扩展也同理
要注意的是,先向右操作和先向左操作在扩展出相同的点的数量的时候的操作数可能是不同的
具体来说,对于样例的0→−1→0→1→2,这是先向左操作的情况,总次数为4
,如果先向右,也就是0→1→2→1→0→−1同样也是四个矿洞,但是操作次数却提高成了5
次
因此我们要分别枚举先向左[0,m]次的情况,再枚举先向右[0,m]次的情况
存在负数不好处理,都加一个偏移量让起点从1
开始
#include <iostream>
#include <queue>
using namespace std;
// 为了保证offset + m不越界
const int N = 4e6 + 10;
int n, m;
// 存放对应坐标的矿洞数量
int a[N];
priority_queue<int, vector<int>, greater<int>> q;
int ans;
int main()
{
cin >> n >> m;
int offset;
for (int i = 0; i < n; i++)
{
int p;
cin >> p;
q.push(p);
}
// 如果存在负轴的点,都加一个偏移量移到正轴上去
offset = min(q.top(), 0);
// 为了前缀和要+1,原来原点的坐标现在变成offset + 1
offset = -offset + 1;
for (int i = 0; q.size(); i++)
{
a[q.top() + offset]++;
q.pop();
}
for (int i = 1; i <= N - 1; i++)
a[i] += a[i - 1];
// 从先向右0次到先向右m次逐个枚举
for (int i = 0; i <= m; i++)
{
int sum = 0;
// 确保剩下的次数能支持向左
if (m - 2 * i >= 0)
// 最多到起点,避免越界
if (offset - (m - 2 * i) >= 1)
sum += a[offset] - a[offset - (m - 2 * i) - 1];
else
sum += a[offset];
sum += a[offset + i] - a[offset];
ans = max(ans, sum);
}
// 从先向左0次到先向左m次逐个枚举
for (int i = 0; i <= m; i++)
{
int sum = 0;
if (offset - i >= 1)
sum += a[offset] - a[offset - i - 1];
else
sum += a[offset];
// 确保剩余次数支持向右移动
if (m - 2 * i > 0)
sum += a[offset + (m - 2 * i)] - a[offset];
ans = max(ans, sum);
}
cout << ans;
return 0;
}