帮佳代子抓小猫的个人思路

题目传送门

进食后人：

a 数组不一定有序。 ~~栽到这个坑的乖乖举个抓抓QWQ~~

思路：

在只有正方向的数轴上走往返运动，首先往返的时间是一致的，路程是一致的，速度是一致的。

根据样例1：

输入：

CPP

3
1 2 6
10

输出：

CPP

抓住第一只猫需要

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)

的时间。

而小猫移动的时间及相对于原位置移动的时间为：

cnt_x = 2\ (cnt_{x - 1} + a_{x - 1})

先初始化第

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;
}

帮佳代子抓小猫的个人思路

文章操作

题目传送门

进食后人：

思路：

Code：

相关推荐

评论

帮佳代子抓小猫的个人思路