题解：B4187 [中山市赛 2024] 糖果共享

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