九度oj 1554 區間問題，九度oj1554區間
原題鏈接：http://ac.jobdu.com/problem.php?pid=1554
由數列的前綴和：$\begin{align*}\Large{} S_n &=\Large{}\sum_{i=1}^{n}{{a_i}} \ \ \ \ i=1,2,3...n\end{align*}$
由於：$\begin{align*}\Large{} S_n -S_{n-1}&=\Large{}a_n \end{align*}$
所以區間$\begin{align*}\Large{} [i,j]\end{align*}$ 之和，$\begin{align*}\Large{} S_j -S_{i-1}&=\Large{}a_i+a_{i+1}+...+a_j\ \ \ 1 \leq i,j,\leq n\end{align*}$
由題意給定一個數組，判斷數組內是否存在一個連續區間，使其和恰好等於給定整$\begin{align*}\Large{} k \end{align*}$
其實就是判斷$\begin{align*}\Large{} Sum[j] -Sum[i]=k\end{align*}$是否成立。
暴力的方法直接枚舉，由於$\begin{align*}\Large{} n=10000\end{align*}$會$\begin{align*}tle\end{align*}$。
現在我們換個思路，試試二分，考慮開個結構體數組，保存原數組的前綴和+原來的位置。
然後對其排序，再進行二分。但這樣可能會出錯，所以再判斷一下，即可。
懶得啰嗦了，直接看代碼吧。。
![]()
1 #include<algorithm>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<cstdio>
6 using std::sort;
7 using std::lower_bound;
8 const int Max_N = 10010;
9 int arr[Max_N], sum[Max_N], temp[Max_N];
10 struct Node {
11 int v, pos;
12 bool operator<(const Node &x) const {
13 if (v == x.v) return pos < x.pos;
14 return v < x.v;
15 }
16 }rec[Max_N];
17 void solve(int n, int k) {
18 int p = 0;
19 for (int i = 0; i < n; i++) {
20 p = lower_bound(temp + 1, temp + n, sum[i] + k) - temp;
21 if (p == n && sum[n] != k) continue;
22 if (rec[p].pos > i && rec[p].v == sum[i] + k) {
23 printf("%d %d\n", i + 1, rec[p].pos);
24 return;
25 } else {
26 p++;
27 while (rec[p].v == sum[i] + k) {
28 if (rec[p].pos > i) {
29 printf("%d %d\n", i + 1, rec[p].pos);
30 return;
31 }
32 p++;
33 }
34 }
35 }
36 puts("No");
37 }
38 int main() {
39 #ifdef LOCAL
40 freopen("in.txt", "r", stdin);
41 freopen("out.txt", "w+", stdout);
42 #endif
43 int n, k;
44 while (~scanf("%d", &n)) {
45 for (int i = 1; i <= n; i++) {
46 scanf("%d", &arr[i]);
47 sum[i] = sum[i - 1] + arr[i];
48 rec[i].v = sum[i], rec[i].pos = i;
49 }
50 scanf("%d", &k);
51 sort(rec + 1, rec + n);
52 for (int i = 1; i <= n; i++) temp[i] = rec[i].v;
53 solve(n, k);
54 }
55 return 0;
56 }
View Code
