帮佳代子抓小猫的个人思路
RedWen_shuo
·
·
题解
题目传送门
进食后人：
a 数组不一定有序。 栽到这个坑的乖乖举个抓抓QWQ
思路：
在只有正方向的数轴上走往返运动，首先往返的时间是一致的，路程是一致的，速度是一致的。
根据 样例1：
输入：
3
1 2 6
10
输出：
2
抓住第一只猫需要 1 秒，往返运动 2 秒，第二只猫相对于原来位置移动了 2 ，可以用一个 cnt 数组存储每只小猫移动的距离，即第 x 只小猫移动的距离为 cnt_x。
设第 x 只小猫初始在 a_x 的位置，则小猫与原点的距离为原来位置加上移动的距离，即： S_x = (cnt_x + a_x)。
由速度差为 1 可以知道想要追上第 x 小猫，需要 t_{\ 单程} = (cnt_x + a_x) 的时间。
往返时间相同，则一次往返要 t_{\ 往返} = 2\ (cnt_x + a_x) 的时间。
而小猫移动的时间及相对于原位置移动的时间为：
先初始化第 $0$ 只小猫 $cnt_0 = 0,a_0 = 0$，根据递推原理求出 $cnt_1,cnt_2,cnt_3......cnt_n$：
```cpp
cnt[i] = cnt[i - 1] + 2 * (cnt[i - 1] + a[i - 1]);
```
由于 $cnt$ 数组每次数值只用一次，可以直接把 $cnt$ 数组压缩成变量：
```cpp
cnt += 2 * (cnt + a[i]);
```
每次将 $cnt$ 与总时间比较来判断是否可以继续抓。
## Code：
```cpp
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
template<typename T> void re(T&x){x = 0; int sign = 1; char c;do{c = getchar(); if (c == '-') sign = -1;}while(!isdigit(c)); do{x = x * 10 + c - '0'; c = getchar();}while(isdigit(c)); x *= sign;}
void write(int x){if (x < 0) x = -x, putchar('-'); if (x < 10) putchar(x + '0'); else write(x / 10), putchar(x % 10 + '0');}
const int N = 2e6 + 100;
ll n;
ll t;
ll a[N];
bool cmp(ll x, ll y){
return x < y;
}
int main(){
re(n);
for (int i = 1; i <= n; i ++) re(a[i]);
re(t);
ll ans = 0, cnt = 0;
sort(a + 1, a + n + 1, cmp);
ll l = 1;
while (cnt <= t){
cnt += (a[l] + cnt) * 2;
if (cnt > t) break;
ans ++;
l ++;
}
printf("%lld", ans);
return 0;
}
```