N^2的算法超时

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

 

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #define INF 0x7fffffff  7 using namespace std;  8 set
          
            S; 9 long long a,aa,aaa; 10 void check(long long x,long long &y) 11 { 12 if(abs(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
            
             >aa; 30 a+=aa; 31 check(a,ans); 32 set
             
              ::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 }