PAT甲级1046 Shortest Distance：[C++题解]前缀和

文章目录

• • • 题目分析
    • 题目链接

题目分析

来源:acwing

分析:

用前缀和快速求出一段的和。注意求两段，取最小值。

ac代码

#include<bits/stdc++.h> using namespace std;const int N = 1e5+10; int a[N]; int s[N]; int n ,m;int main(){cin >> n;for(int i = 1; i<= n; i++) cin>> a[i], s[i] = s[i-1] +a[i];cin >> m;while(m--){int x, y;cin >> x >> y;if( x > y) swap(x,y);int d1 = s[y-1] -s[x-1];int d2 = s[n]-s[y-1] +s[x-1];cout<< min(d1,d2)<<endl;} }

题目链接

PAT甲级1046 Shortest Distance
https://www.acwing.com/problem/content/1532/

总结

以上是生活随笔为你收集整理的PAT甲级1046 Shortest Distance：[C++题解]前缀和的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。