本文最后更新于 721 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
- 前缀和。
- 由于出口为环状,故将数组首尾相连。
- 构造前缀和数组,即可得到在任意出口顺时针方向或逆时针向走到对应出口的距离之和。
- 对于每次询问,输出顺时针和逆时针方向上,两个出口最短的距离即可。
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N = 1e6 + 3; |
| |
| typedef long long LL; |
| |
| int a[N]; |
| |
| void solve(){ |
| int n; cin >> n; |
| for(int i = 1; i <= n; i ++){ |
| cin >> a[i]; a[i + n] = a[i]; |
| } |
| for(int i = 1; i <= n * 2; i ++) a[i] += a[i - 1]; |
| int m; cin >> m; |
| while(m --){ |
| int l, r; cin >> l >> r; |
| if(l > r) swap(l, r); |
| cout << min(a[r - 1] - a[l - 1], a[l + n - 1] - a[r - 1]) << endl; |
| } |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |