URAL1010[Discrete Function]

可以证明这样的两个点一定是相邻的。
如图:
URAL1010[Discrete Function] - 天之骄子 - 天之骄子的家


明显红线没有绿线优,绿线又没有紫线优,如此一直推,会发现最后一定是两个相邻点。
CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-13


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


using std::endl;


#include <sstream>


using std::stringstream;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


#include <cassert>


//using std::assert;


 


class Application


{


      static const int oo=~(1<<31);


      int N;


      vector<double> f;


      public:


      Application()


      {


                   cin>>N;


                   f.resize(N);


                   for (int i=0;i<N;i++)


                       cin>>f[i];


      }


      int run()


      {


          //max{abs(f[i-1]-f[i]) ,2<=i<=N}


          double max=-oo;


          int max_i;


          for (int i=1;i<N;i++)


          {


              double abs_k=f[i-1]>f[i]?f[i-1]-f[i]:f[i]-f[i-1];


              if (abs_k>max)


              {


                 max=abs_k;


                 max_i=i;


              }


          }


          cout<<max_i+11<<” “<<max_i+1<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}