摘要
Title: 4455. 出行计划
Tag: 差分、前缀和
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

4455. 出行计划

• 题意

  第25次CCF计算机软件能力认证

  略

• 思路

  由于在考场上做了，所以思路真的懒得想了，下面是某大佬的分析

  • t时刻做核酸，可以在[t + k, t + k + c - 1]进入某个场所，其中c为进入场所时所需的单位时间数
  • 若在ti时刻进入某场所，即要求ti >= t + k，且ti <= t + k + c - 1，可以解得ti - k - c + 1 <= t <= ti - k
  • 所以若在时刻q做了核酸，那么可以进入场所的区间为[ti - k - c + 1, ti - k],即只需看时间q落在多少个区间内部，然后让这个区间内所有数加一即可，这可以利用差分来做。
  • 对差分数组求前缀和数组即可得到原数组

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-01-14 21:16:39
  * @FilePath: \Acwing\4455\4455.cpp
  * @LastEditTime: 2023-01-14 21:17:00
  */
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #undef int
  
  #define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \
      ios::sync_with_stdio(false);                                                                                       \
      cin.tie(nullptr);                                                                                                  \
      cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;
  const int N = 2e5 + 10;
  
  int n, m, k;
  int d[N];
  
  signed main()
  {
      scanf("%d%d%d", &n, &m, &k);
      for (int i = 1; i <= n; i++)
      {
          int t, c;
          scanf("%d%d", &t, &c);
          d[max(1, t - k - c + 1)]++;
          d[max(1, t - k + 1)]--;
      }
      for (int i = 1; i <= N; i++)
      {
          d[i] += d[i - 1];
      }
      for (int i = 1; i <= m; i++)
      {
          int q;
          scanf("%d", &q);
          printf("%d\n", d[q]);
      }
      return 0;
  }