Firecrackers
题意
一个囚犯和一个守卫 在一维坐标上移动，每一秒按顺序发生以下三件事
囚犯向左或向右移动一步 或者呆在原地， 如果囚犯呆在原地， 那么它可以在所处的位置放下一个鞭炮
一些鞭炮可能会爆炸 对于第i个 鞭炮 会在被放置后的 s i 秒爆炸守卫会朝囚犯的方向前进一步问：在囚犯被守卫捉住前 最多能爆炸多少鞭炮
思路
首先要知道 一个格子可以同时存在多个鞭炮… 一开始没注意到这一点死活解不出来
其次 先放鞭炮再跑 和先跑再放鞭炮，肯定是前者更优，因为在跑的过程中，鞭炮已经在倒计时了，所以我们可以让囚犯在没被逮到之前一直处于出生点，然后不断地放鞭炮，直到守卫到他旁边一格，以 b>a 为例 a>b 同理)，一共最多可以放 abs(b−a)−1 个鞭炮 然后囚犯可以向守卫来的反方向逃跑最多 a − 1秒 用tot 表示当前距离囚犯被抓还有几秒 如果鞭炮的 s i 小于等于当前的tot 则可以爆炸，因为放下鞭炮需要 1 秒 所以更新 tot−−
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } const int N = 200010; LL n, m, a, b; LL c[N]; bool cmp(LL a, LL b) { return a > b; } void solve() { scanf("%lld%lld%lld%lld", &n, &m, &a, &b); for (int i = 1; i <= m; ++i)scanf("%lld", &c[i]); sort(c + 1, c + m + 1, cmp); int tot = a - 1; if (a > b)tot = n - a; int boom = abs(b - a) - 1; tot += boom; int cnt = 0; for (int i = 1; i <= m; ++i) { if (cnt == boom)break; if (c[i] <= tot) { cnt++; tot--; } } cout << cnt << endl; } int main() { int t; cin >> t; while(t--) solve(); return 0; }
