题目:http://pat.zju.edu.cn/contests/pat-a-practise/1046
题解:
看题目还以为是图方面的问题。。
题意就是给一个N节点的环,问某两个节点之间的最短距离是多少。
首先对N个节点计算出从第1个节点到第i 个节点的距离,之后查询的时候只要相减就能得出答案。
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<string> #include<vector> #include<queue> #include<stack> #include<map> #include<algorithm> using namespace std; int num[100005]; int main() { int n,m,a,b,summ=0; scanf("%d",&n); num[0]=0; for(int i=1;i<=n;++i) { scanf("%d",&a); summ+=a; num[i]=summ; } scanf("%d",&m); int ans; for(;m--;) { scanf("%d%d",&a,&b); if(a>b)//交换两数 { a=a^b; b=a^b; a=a^b; } ans=num[b-1]-num[a-1]; printf("%d\n",num[n]-ans>ans?ans:num[n]-ans); } return 0; }