自动搬运

查看原文

来自洛谷，原作者为

	Sweet_2013 今夕是何年？ | 234粉爆我妹的照片，求关 | 互关条件 /training/813543

搬运于2025-08-24 21:17:42，当前版本为作者最后更新于2025-03-06 19:49:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 定义 $que$，用于存储需要更新的时间位置。
• 遍历环形数组 $t$ 的每个位置 $i$，对于每个位置 $i$，检查其后继位置的时间是否大于 $t_i+p_i$，并将后继位置加入队列 $que$，以便后续进一步更新。
• 使用队列 $que$ 进行动态更新
  • 每次从队列中取出一个位置 $x$，检查其后继位置是否需要更新。
  • 如果需要更新，则更新后继位置的时间，并将其加入队列，以便后续进一步更新。
• 这个过程会不断重复，直到队列为空，确保所有需要更新的位置都被更新。
• 输入查询次数 $q$。对于每次查询，输入查询位置 $x$，并输出该位置的时间 $t_{x-1}$。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
long long t[MAXN], p[MAXN], n, q, x;
queue<int> que;//这个就是队列了。
int main() {
    cin>> n;
    for(int i=0;i<n;i++) cin>> t[i];
    for(int i=0;i<n;i++) cin>> p[i];
    for (int i=0;i<n;i++) {
        if(t[(i+1)%n]>t[i]+p[i]) {
            t[(i+1)%n]=t[i]+p[i];//对于每个位置 i，检查其后继位置 (i+1)%n 的时间是否大于 t[i]+p[i]。
            que.push((i+1)% n);//如果满足条件，则更新后继位置的时间为 t[i] + p[i]，并将后继位置加入队列 que，以便后续进一步更新。
        }
    }
    while(!que.empty()) {//队列没空。
        int x=que.front();
        que.pop();//取出位置 x。
        if (t[(x+1)%n]>t[x]+p[x]) {//检查其后继位置 (x+1)%n 是否需要更新。
            t[(x+1)%n]=t[x]+p[x];
            que.push((x+1)%n);//如果需要更新，则更新后继位置的时间，并将其加入队列，以便后续进一步更新。
        }
    }
    cin>> q;
    while (q--) {
        cin>> x;
        cout<<t[x-1]<<endl;//输出该位置的时间 t[x-1]。
    }
    return 0;
}