九度 1376 最近零子序列

http://ac.jobdu.com/problem.php?id=1376

N^2的算法超时

优化算法想了好久没想出来，就当是学习一下STL的set了吧

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <math.h>
 4 #include <set>
 5 #include <iostream>
 6 #define INF 0x7fffffff
 7 using namespace std;
 8 set<long long> S;
 9 long long a,aa,aaa;
10 void check(long long x,long long &y)
11 {
12     if(abs(x)<abs(y)){
13         y=x;
14     }else if(abs(x)==abs(y)&&x>=0){
15         y=x;
16     }
17 }
18 int main()
19 {
20     int N,ans=INF;
21     while(scanf("%d",&N)!=EOF){
22         aa=0;
23         int i;
24         S.clear();
25         cin>>a;
26         S.insert(a);
27         long long ans=a;
28         for(i=1;i<N;i++){
29             cin>>aa;
30             a+=aa;
31             check(a,ans);
32             set<long long>::iterator it;
33             it=S.lower_bound(a);
34             if(it==S.end()){
35                 aaa=a-*S.rbegin();
36                 check(aaa,ans);
37             }else{
38                 aaa=a-*it;
39                 check(aaa,ans);
40                 it--;
41                 aaa=a-*it;
42                 check(aaa,ans);
43             }
44             S.insert(a);
45         }
46         printf("%ld\n",ans);
47     }
48 }