摘要
Title: 1530. 最短距离
Tag: 前缀和
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1530. 最短距离

• 题意

  一个环形高速公路上有 N 个出口，共有 M 次询问，每次询问你需要回答其中两个出口之间的最短距离是多少。

• 思路

  可以用前缀和解决，一共就是两条路，两条路的和为数组的总和，判断一下哪个更短即可

• 代码

  #include <bits/stdc++.h>
  #define int long long
  #define SZ(X) ((int)X.size())
  
  using namespace std;
  
  signed main()
  {
      int n;
      cin >> n;
      vector <int> v (n + 1);
      for(int i = 1; i <= n; ++ i){
          cin >> v[i];
      }
      int sum = accumulate(v.begin(), v.end(), 0);
      for(int i = 1; i <= n; ++ i){
          v[i] += v[i - 1];
      }
      int m;
      cin >> m;
      for(int i = 0; i < m; ++ i){
          int l, r;
          cin >> l >> r;
          if(l > r) swap(l, r);
          r--, l--;
          cout << min(v[r] - v[l], sum - v[r] + v[l]) << '\n';
      }
      return 0;
  }