题目描述:
某一天,老鼠杰瑞抓住了一个机会,成功的到达了冰箱的附近,正当杰瑞打开冰箱门,想要享受美味的奶酪的时候,没想到冰箱里的奶酪太多了,奶酪洒了一地。汤姆猫听到了这个动静,正在火速赶往冰箱想要抓住杰瑞。杰瑞凭借与汤姆多年对抗的经历,仅凭借汤姆的脚步声便能推断汤姆还有多久抵达,现在,杰瑞并不怕汤姆,但汤姆抵达后必然影响杰瑞吃奶酪。于是杰瑞想要知道,在汤姆到达前,自己最多能吃到多少奶酪。
现在已知杰瑞与所有奶酪刚好排成一条直线,用坐标记录每个奶酪的位置,杰瑞一开始的坐标为0,杰瑞移动一个单位距离需要一个单位时间
由于杰瑞能一口吃下一整块奶酪,因此杰瑞吃奶酪的过程并不会花任何时间
输入格式:
第一行两个正整数t,n ,表示汤姆抵达需要的时间和奶酪的数量,
第二行n个整数,表示奶酪的坐标c。
输出格式: 一个整数,表示杰瑞最多能吃到的奶酪数量。
输入:
30 16
8 5 18 2 11 0 7 -14 -5 17 -11 15 -6 -16 10 1
输出:
13
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int N = 2e5 + 10;
int n, m, l, r, t, mid, ans, a[N];
bool check(int x)
{
for(int i = 0; i <= n - x; i ++)
{
int j = i + x - 1;
if(a[j] <= 0&&-a[i] <= t) return true;
if(a[i] >= 0&&a[j] <= t) return true;
if(a[i] <= 0&&a[j] >= 0)
if(min(-a[i], a[j]) + (a[j] - a[i]) <= t) return true;
}
return false;
}
void solve()
{
cin >> t >> n;
for(int i = 0; i < n; i ++)
cin >> a[i];
sort(a, a + n);
l = 1, r = n;
while(l <= r)
{
mid = l + (r - l) / 2;
if(check(mid)) l = mid + 1, ans = mid;
else r = mid - 1;
}
cout << ans << '\n';
}
signed main()
{
IOS;
int _ = 1;
// cin >> _;
while(_ --) solve();
return _ ^ _;
}