2021四川省赛J

2021四川省赛J

2023大厂真题提交网址(含题解):

www.CodeFun2000（101.43.147.120/）

最近我们一直在将收集到的机试真题制作数据并搬运到自己的OJ上，供大家免费练习,体会真题难度。现在OJ已录入50+道2023年最新大厂真题，同时在不断的更新。同时，可以关注"塔子哥学算法"公众号获得每道题的题解。

题目大意：

一维数轴 [ 1 , 1 e 9 ] [1,1e9] [1,1e9]上有 n n n个蚂蚁，每个蚂蚁有一个初始方向(左右).然后开始以1的速度运动.两蚂蚁碰撞后反向.在数轴两端有两个石头，每个石头分别有 a , b a,b a,b的耐性(指被撞多少次后碎掉).蚂蚁撞上石头后也反向。问所有蚂蚁全部掉落的时间.
n ≤ 1 e 5 , a , b ≤ 1 e 9 n leq 1e5 , a , b leq 1e9 n≤1e5,a,b≤1e9.

题目思路:

1.每隔 2 L 2L 2L,每个蚂蚁会回到自己的原位置且方向不变.所以我们可以直接模拟最后一轮的情况.
2.碰撞看作穿过.
3.最后一轮,使用两个队列表示往左/右的蚂蚁。每次选取时间小的队头,拿出来塞到另一个队列里即可.
4.用优先队列模拟该过程代码更简洁. 复杂度: O ( n l o g n ) O(nlogn) O(nlogn)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vll vector<ll>
#define fi first
#define se second
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const ll len = 1e9;
const ll inf = 9e18;
ll a[maxn] , d[maxn];
priority_queue<ll , vector<ll> , greater<ll>> ql , qr;
int main()
{ios::sync_with_stdio(false);int n , x , y; cin >> n >> x >> y;for (int i = 1 ; i <= n ; i++){cin >> a[i];}for (int i = 1 ; i <= n ; i++){cin >> d[i];}ll ti = min(x , y) / n * (len * 2 + 2);ll g = min(x , y) / n * n;x -= g;y -= g;for (int i = 1 ; i <= n ; i++){if (d[i]) qr.push(ti + len - a[i] + 1);else ql.push(ti + a[i]);}ll res = ti;while (ql.size() || qr.size()){ll g;if (ql.size()){g = ql.top();res = max(res , g);ql.pop();if (x){qr.push(g + len + 1);x--;}}if (qr.size()){g = qr.top();res = max(res , g);qr.pop();if (y){ql.push(g + len + 1);y--;}}}cout << res << endl;return 0;
}