gym103117J. Ants

題意：

n個螞蟻在長度為1e9+1的木棍上，第i個螞蟻在ai位置上，朝向為0/1（0表示左，1表示右）,如果螞蟻相遇則彼此調轉方向。木棍兩側分別有厚度為a和b的墻，螞蟻每撞一次墻，墻的厚度就會減1，當墻撞沒時，螞蟻就會直接掉下去，問最后一個螞蟻掉下去的時間？

題解：

模擬題
有幾點注意：

螞蟻相遇調轉方向可以相當于方向沒變

一個螞蟻需要撞兩次墻才能回到原先的位置(墻沒撞開)，相當于周期為2len，每個周期，每只螞蟻會對兩側的墻各撞一次

所以我們可以將前面整數個周期都算完，最后就剩下一輪，直接模擬完事

思路很簡單，但是最后一輪的模擬很麻煩，我和隊友調了4個小時才改出來，但是發現網上有很多簡易的方法
我們用兩個隊列分別存向左向右的螞蟻，每次取出兩個隊列首的元素，比較兩個元素誰離端點更近，更近的會先撞墻，然后掉頭，加入另一個隊列中，直到墻撞開

代碼：

const int N = 2e6 + 5;int n, a, b, p[N], d[N], L = 1e9 + 1;LL s, ans; LL q1[N], q2[N]; int hh = 1, tt, h = 1, t;void inline work1() {LL u = q1[hh++];if (a) {a--;q2[++t] = u + L;}else {ans=max(ans,u); } }void inline work2() {LL u = q2[h++];if (b){b--;q1[++tt] = u + L;} else {ans=max(ans, u);} }int main() {read(n), read(a), read(b);for (int i = 1; i <= n; i++) read(p[i]);for (int i = 1; i <= n; i++) read(d[i]);LL tmp = min(a, b) / n;a -= n * tmp, b -= tmp * n;s = tmp * L * 2;for (int i = 1; i <= n; i++)if (d[i] == 0) q1[++tt] = p[i];//左 for (int i = n; i; i--)if (d[i] == 1) q2[++t] = L - p[i];//右 while (hh <= tt || h <= t) {if (h > t || (hh <= tt && q1[hh] < q2[h])) work1();//左邊先到 else work2();}printf("%lld\n", ans + s);return 0; }

我和隊友的代碼：
就是純模擬，討論四種情況

// Problem: Ants // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/17624/J // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC target("avx") //#pragma GCC optimize(2) //#pragma GCC optimize(3) //#pragma GCC optimize("Ofast") // created by myq #include <algorithm> #include <cctype> #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> using namespace std; typedef long long ll; #define x first #define y second typedef pair<int, int> pii; const int N= 1000010; const int mod= 998244353; #define int long long int a[N]; int d[N]; int n, l, r; signed main() {ios::sync_with_stdio(0);cin >> n >> l >> r;int len= 1e9 + 1;int j= 0;for (int i= 1; i <= n; i++) {cin >> a[i];}int lcnt= 0;int rcnt= 0;int res1= 0;int res2= 0;for (int i= 1; i <= n; i++) {cin >> d[i];if (!d[i])lcnt++, res1= max(res1, a[i]);elsercnt++, res2= max(res2, len - a[i]);}int tt= min(l / n, r / n);int res= 0;res+= 2 * len * tt;l-= tt * n;r-= tt * n;if (l < lcnt && r < rcnt) {// if (n == 11)// cout << 1 << endl;vector<int> vv;vector<int> vv2;for (int i= 1; i <= n; i++)if (d[i])vv2.push_back(len - a[i]);for (int i= 1; i <= n; i++)if (!d[i])vv.push_back(a[i]);int L= (l == 0 ? (vv.size() ? vv.back() : 0) : vv[l - 1] + len);int R= (r == 0 ? (vv2.size() ? vv2[0] : 0) : vv2[(int)vv2.size() - r] + len);res+= max(L, R);}else if (l < lcnt && r >= rcnt) {// if (n == 11)// cout << 2 << endl;r-= rcnt;vector<int> vv;vector<int> vv2;for (int i= 1; i <= n; i++)if (d[i])vv2.push_back(len - a[i]);for (int i= 1; i <= n; i++)if (!d[i])vv.push_back(a[i]);if (l) {int tmp= vv[l - 1] + len;int tmp2= 0;int tmp3= 0;if (rcnt) {tmp2+= vv2[0] + len;}if (r) {int tr= min(r, l);tmp3= vv[tr - 1] + 2 * len;}res+= max({tmp, tmp2, tmp3});}else {res+= max((vv2.size() ? vv2[0] + len : 0ll), vv.back());}}else if (l >= lcnt && r < rcnt) {// if (n == 11)// cout << 3 << endl;vector<int> vv;vector<int> vv2;l-= lcnt;for (int i= 1; i <= n; i++)if (d[i])vv2.push_back(len - a[i]);for (int i= 1; i <= n; i++)if (!d[i])vv.push_back(a[i]);if (r) {int tmp= 0;int tmp2= vv2[vv2.size() - r] + len;int tmp3= 0;if (lcnt) {tmp+= vv.back() + len;}if (l) {int tr= min(l, r);tmp3= 2 * len + vv2[vv2.size() - tr];}res+= max({tmp3, tmp, tmp2});}else {res+= max((vv.size() ? len + vv.back() : 0ll), vv2[0]);}}else if (l >= lcnt && r >= rcnt) {// if (n == 11)// cout << 4 << endl;res+= len;l-= lcnt;r-= rcnt;lcnt= 0;rcnt= 0;// if(n==87)// cout<<res<<endl;for (int i= 1; i <= n; i++) {a[i]= len - a[i];d[i]^= 1;if (!d[i])lcnt++;elsercnt++;}if (l < lcnt && r < rcnt) {// if (n == 11) {// cout << 41 << endl;// cout << l << " " << r << endl;// cout << lcnt << " " << rcnt << endl;// }vector<int> vv;vector<int> vv2;for (int i= 1; i <= n; i++)if (d[i])vv2.push_back(len - a[i]);for (int i= 1; i <= n; i++)if (!d[i])vv.push_back(a[i]);reverse(vv.begin(), vv.end());reverse(vv2.begin(), vv2.end());// sort(vv.begin(), vv.end());// sort(vv2.begin(), vv2.end(), greater<int>());// if(n==87)// cout<<vv[l-1]+len<<" "<< vv2[(int)vv2.size() - r] + len<<" "<<vv.back()<<" "<<vv2[0]<<endl;int L= (l == 0 ? (vv.size() ? vv.back() : 0) : vv[l - 1] + len);int R= (r == 0 ? (vv2.size() ? vv2[0] : 0) : vv2[(int)vv2.size() - r] + len);res+= max(L, R);}else if (l < lcnt && r >= rcnt) {// if (n == 11)// cout << 42 << endl;r-= rcnt;vector<int> vv;vector<int> vv2;for (int i= 1; i <= n; i++)if (d[i])vv2.push_back(len - a[i]);for (int i= 1; i <= n; i++)if (!d[i])vv.push_back(a[i]);reverse(vv.begin(), vv.end());reverse(vv2.begin(), vv2.end());if (l) {// if(n==59)// cout<<l<<" "<<r<<" "<<lcnt<<" "<<rcnt<<endl;int tmp= vv[l - 1] + len;int tmp2= 0;int tmp3= 0;if (rcnt) {tmp2+= vv2[0] + len;}if (r) {int tr= min(r, l);tmp3= vv[tr - 1] + 2 * len;}res+= max({tmp, tmp2, tmp3});}else {res+= max((vv2.size() ? vv2[0] + len : 0ll), vv.back());}}else if (l >= lcnt && r < rcnt) {if (n == 11)cout << 43 << endl;vector<int> vv;vector<int> vv2;l-= lcnt;for (int i= 1; i <= n; i++)if (d[i])vv2.push_back(len - a[i]);for (int i= 1; i <= n; i++)if (!d[i])vv.push_back(a[i]);reverse(vv.begin(), vv.end());reverse(vv2.begin(), vv2.end());if (r) {int tmp= 0;int tmp2= vv2[vv2.size() - r] + len;int tmp3= 0;if (lcnt) {tmp+= vv.back() + len;}if (l) {int tr= min(l, r);tmp3= 2 * len + vv2[vv2.size() - tr];}res+= max({tmp3, tmp, tmp2});}else {res+= max((vv.size() ? len + vv.back() : 0ll), vv2[0]);}}}cout << res << endl;return 0; } /** * In every life we have some trouble * When you worry you make it double * Don't worry,be happy. **/ 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的gym103117J. Ants的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。