1046 Shortest Distance (20分)

先把距离算出来，用数组存储起来，否则每次查询都就要重新算一次，导致超时。

 1 #include <iostream>
 2 using namespace std;
 3 int main()
 4 {
 5     int n;     cin >> n;
 6     int sum = 0;
 7     unsigned long int* d = new unsigned long int[n];
 8     unsigned long int * dst = new unsigned long int[n];
 9     for (int i = 0; i < n; i++)
10     {
11         dst[i] = sum;//顺时针方向各点到第一个点的距离
12         cin >> d[i];
13         sum += d[i];
14     }
15     int k; cin >> k;
16     for (int i = 0; i < k; i++)
17     {
18         int n1, n2, res1 = 0, res2 = 0;
19         cin >> n1 >> n2;
20         res1 = n1<n2?dst[n2 - 1] - dst[n1 - 1]:dst[n1-1]-dst[n2-1];
21         cout << (sum-res1 < res1 ? sum-res1 : res1);
22         if (i != k - 1)cout << endl;
23     }
24     return 0;
25 }