亂八七糟的代碼

第四章  效率

······條款16 記住80-20準則

大約20%的代碼使用了80%的資源，程序的整體性能是由該程序的一小部分代碼所決定的~

可行的辦法是使用程序分析器（profiler）來找到導致性能瓶頸的拿20%的程序~

而且要針對造成瓶頸的資源來使用相應的分析器~

······條款17  考慮使用延遲計算

延遲計算： 也就是說知道程序要求給出結果的時候才進行運算~ 很好理解，和操作系統中的cow copy on write 一個原理~

四個使用場景：

~1~ 引用計數 ：

　　class String{…};

String s1 = “hello”;

String s2 = s1 ;      //call string Copy ctor

通常情況下，s2賦值后會有一個hello的拷貝，者通常需要使用new操作符分配內存，之后strcpys1

的數據給他，但如果下面的操作如下的話：

cout << s1 ;

cout << s1 + s2;

這種情況下如果只增加s1的引用計數，而s2只是共享s1的值就可以了。只有在需要對s2進行修改或者s1進行修改時，才需要真正拷貝給s2一個副本，引用計數的實現在29條款

~2~區分讀寫操作

如： String s = “homer’s all”;

cout<< s[3];

s[3] = ‘x’;

在進行讀操作時，使用引用計數是開銷很小的，然而寫操作必須生成新的拷貝。通過條款30的代理類我們可以把判斷讀寫操作推遲到我們能夠決定哪個是正確操作的時候

~3~延遲讀取

假設程序使用了包含許多數據成員的大對象，這些對象必須在每次程序運行的時候保留下來，因此存進了數據庫。某些時候從database中取出所有數據是沒有必要的，比如他只訪問該對象中的一個數據成員。此時，應該對對象進行處理，只有對象內部某一個特定的數據成員被訪問的時候才把他取出來。類似于os中的按需換頁~

class LargeObject{

    LargeObject(ObjectID id);

const string& field1() const;

int field2() const;

double field3() const;

const string& field4() const;

private:

ObjectID id;

mutable string* field1value;

mutable int   * fieldValue;

};

LargeObject::LargeObject(ObjectID id):oid(id),fieldValue(0),…{}

const string& LargeObject::field1()const{

   if(fieldValue == 0){

       //read the data for field 1 from database and make field1 point to it

   }

   return  *field1Value;

}

實施lazy fetching 任何成員函數都需要初始化空指針以指向有效數據。但是const成員函數中，試圖修改數據編譯器會報錯。所以聲明字段指針為 mutable ，表示任何函數都可以修改,即便在const成員函數中也可以~ 條款28中的智能指針可以讓這一方法更靈活

~3~延遲表達式求值

數值計算領域，也在使用延遲計算。例如

matrix<int> m1(1000,1000);

matrix<int> m2(1000,1000);

matrix<int> m3 = m1 + m2;

如果此時計算出m3的話運算量非常之大~

但是如果此時程序為：

m3 = m4*m1;

那么剛才的計算就沒必要了

如果cout<< m3[4];

我們只需要計算m3[4]就可以了，其他的值等到確實需要他們的時候才予以計算~如果運氣夠好的話永遠不需要計算~

總結，延遲計算只有當軟件在某種程度下可以被避免時候才有意義~只有延遲計算得到的好處大于設計它與實現它花費的精力時才有意義~

·······條款18： 分期攤還預期的計算開銷

提前計算~ over-eager evaluation 在系統要求你做某些事情之前就做了他~

例如：大量數據的集合

template<class NumericalType>

class DataCollection}{

public:

  NumericalType min() const;

  NumericalType max() const;

  NumericalType avg() const;

};

使用提前計算，我們隨時跟蹤目前集合的最大最小平均值，這樣 min max avg被調用時候，我們可以不用計算立刻返回正確的數值~~

提前計算的思想便是：如果預計某個計算會被頻繁調用，你可以通過設計你的數據結構以更高效的辦法處理請求，這樣可以降低每次請求的平均開銷~

最簡單的做法為 緩存已經計算過并且很可能不需要重新計算的那些值~

例如在數據庫中存有很多辦公室的電話號碼，程序在每次查詢電話時先查詢本地的緩存如果沒找到再去訪問數據庫，并且更新緩存，這樣使用緩存平均訪問時間要大大減小。

預處理也是一種策略。

例如設計動態數組的時候，當索引下標大于已有最大范圍時候，需要new出新的空間，如果申請兩倍于索引的大小的話就可以避免頻繁的申請操作~~~

········條款 19 ： 了解臨時對象的來源

如果一個對象被創建，不是在堆上，沒有名字，那么這個對象就是臨時對象。

通常產生于： 為了使函數調用能夠成功而進行的隱式轉換，或者函數返回對象是進行的隱式轉換。由于構造和析構他們帶來的開銷可以給你的程序帶來顯著的影響，因此有必要了解他們~

~1首先考慮為了函數調用能通過產生的臨時對象的情況

傳給某個函數的對象的類型和這個函數所綁定的參數類型不一致的情況下會出現這種情況。

例如：

size_t count(const string& str,char ch);

函數定義為計算str中ch的數量

char buffer[100];

cout<<count(buffer,‘c’);

傳入的是一個char數組，此時編譯器會調用str的構造函數，利用buffer來創建一個臨時對象。

在調用完countChar語句后這個臨時對象就被自動銷毀了~

僅當傳值或者const引用的時候才會發生這樣的類型轉換~當傳遞一個非常量引用的時候，不會發生。

void uppercasify(string& str); //change all chars in str to upper case;

在這個例子中使用char數組就不會成功~

因為程序作者聲明非常量引用也就是想讓對引用的修改反映在他引用的對象身上，但是如果此時生成了臨時對象，那么這些修改只是作用在臨時對象身上，也就不是作者的本意了。所以c++禁止非常量引用產生臨時對象。

~2 函數返回對象時候會產生臨時對象

例如： const Number operator + ( const Number& lhs,const Number& rhs);

這個函數返回一個臨時對象，因為他沒有名字，只是函數的返回值。

條款20中 ，會介紹讓編譯器對已經超出生存周期的臨時對象進行優化

········條款20： 協助編譯器實現返回值優化

返回值優化：返回帶有參數的構造函數。

cosnt Rational operator * (cosnt Rational& lhs,const Rational& rhs){

    return Rational(lhs.numerator()*rhs.numerator(),lhs.denomiator()*rhs.denominator()};

c++允許編譯器針對超出生命周期的臨時對象進行優化。因此如果調用Rational c=a*b；

c++允許編譯器消除operator*內部的臨時變量以及operator*返回的臨時變量，編譯器可以把return表達式所定義的返回對象構造在分配給c的內存上。如果這樣做的話那么調用operator*所產生的臨時對象所帶來的開銷就是0~ 我們可以把operator 聲明為內聯函數而去除調用構造函數帶來的開銷~

#include <iostream>
#include <string>
#include "time.h"
using namespace std;
char buffer[100];
class number{
public:
    const friend  number operator * (const number& rhs,const number lhs);
    number(){}
    number(int b):a(b){}
    number(const number& rhs){
        a = rhs.a;
    }
      int a;
};
const number operator*(const number& rhs,const number lhs){
    number res;
    res.a = rhs.a * lhs.a;
        return res;
    /*return number(rhs.a*lhs.a);*/
}
//CLOCKS_PER_SEC
int main()
{
    clock_t start = clock();
    number A(5);number B(6);
    for(int i=0;i<100000000;i++)
        number C = A*B;

    clock_t end = clock();
    cout<<double(end-start)/CLOCKS_PER_SEC<<endl;
}

通過上面的程序運行 如果沒有返回值優化 運行時間 15.9s 優化后是 10.1s

還是很顯著的么 快了33% ，如果這種情況出現在程序的熱點處~效果就很好了

·········條款21 ： 通過函數重載避免隱式類型轉換

例子：

class upint{

public:

upint();

upint(int value);

};

cosnt upint operator+(const upint&lhs,const upint&rhs);

upint up1,up2;

upint up3 = up1+up2;

upi3 = up1 +10;

upi4 = 10+ upi2;

這些語句也可以通過，因為創建了臨時對象，通過帶有int的構造函數產生了臨時的upint對象，如果我們不愿意為這些臨時對象的產生與析構付出代價，我們需要做什么：

我們聲明 cosnt upint operator+(cosnt upint&lhs,int rhs);

cosnt upint operator+(int lhs,const upint& rhs);

就可以去除臨時對象產生了~

但是如果我們寫了 const upint operator+(int lhs,int rhs); // 錯了~

c++規定，每一個被重載的運算符必須至少有一個參數屬于用戶自定義類型，int并不是自定義類型所以上面的不對的

同樣的如果希望string char* 作為參數的函數，都有理由進行重載而避免隱形類型轉換（僅僅在有必要的時候，也就是說他們可以對程序效率起到很大幫助的時候~）

··········條款： 考慮使用 op = 來取代 單獨的 op運算符

class Rational{

public:

   Rational& operator+=(const Rational& rhs);

   Rational& operator-=(const Rational& rhs);

}

const Rational operator+(cosnt Rational& lhs,const Rational & rhs){

    return Rational(lhs)+=rhs;

}

利用+= -=來實現+ -可以保證運算符的賦值形式與單獨使用運算符之間存在正常的關系。

Rational a,b,c,d,result;

result = a+ b+c+d; // 可能要用到3個臨時對象

result +=a;result+=b;result+=c; //沒有臨時對象

前者書寫維護都更容易，而且一般來說效率不存在問題，但是特殊情況下后者效率更高更可取

注意：

如果+的實現是這樣的：

const T operator+ (constT& lhs,const T&rhs){

     T result(lhs);

     return result += rhs;

}

這個模版中包含有名字對象result，這個對象有名字意味著返回值優化不可用~~~~~~~~·

·······條款23 ： 考慮使用其他等價的程序庫

主旨：

提供類似功能的程序庫通常在性能問題上采取不同的權衡措施，比如iostream和stdio，所以通過分析程序找到軟件瓶頸之后，可以考慮是否通過替換程序庫來消除瓶頸~~~~

······條款24 : 理解虛函數，多重繼承，虛基類以及 RTTI 帶來的開銷

虛函數表：vtabs 指向虛函數表的指針 vptrs

程序中每個聲明了或者繼承了的虛函數的類都具有自己的虛函數表。表中的各個項就是指向虛函數具體實現的指針。

class c1{

   c1();

   virtual ~c1();

   virtual void f1();

   virtual int f2(char c)const;

   virtual void f3(const string& s);

};

c1 的虛函數表包括： c1::~c1 c1::f1 c1::f2 c1::f3

class c2:public c1{

   c2();

   virtual ~c2();

   virtual void f1();

   virtual void f5(char *str);

};

它的虛函數表入口指向的是那些由c1聲明但是c2沒有重定義的虛函數指針：

c2::~c2  c2::f1 c1::f2 c1::f3 c2::f5

所以開銷上： 必須為包含虛函數的類騰出額外的空間來存放虛函數表。一個類的虛函數表的大小取決于它的虛函數的個數，雖然每一個類只要有一個虛函數表，但是如果有很多類或者每個類具有很多個虛函數，虛函數表也會占據很大的空間，這也是mfc沒有采用虛函數實現消息機制的一個原因。

由于每一個類只需要一個vtbl的拷貝，把它放在哪里是一個問題：

一種：為每一個需要vtbl的目標文件生成拷貝，然后連接時取出重復拷貝

或者：更常見的是采用試探性算法決定哪一個目標文件應該包含類的vtbl。試探：一個類的vtbl通常產生在包含該類第一個非內聯，非純虛函數定義的目標文件里。所以上面c1類的vtbl將放在c1::~c1 定義的目標文件里。如果所有虛函數都聲明為內聯，試探性算法就會失敗，在每一個目標文件就會有vtbl。所以一般忽略虛函數的inline指令。

如果一個類具有虛函數，那么這個類的每一個對象都會具有指向這個虛函數表的指針，這是一個隱藏數據成員vptr~被編譯器加在某一個位置。

此處第二個開銷：你必須在每一個對象中存放一個額外的指針~

如果對象很小這個開銷就十分顯著~~因為比例大~

此時 void makeCall(c1* pc1){

   pc1->f1();

}

翻譯為 (*pc1->vptr[i])(pc1);

根據vptr找到vtbl 這很簡單，

在vtbl找到調用函數對應的函數指針，這個步驟也很簡單，因為編譯器為虛函數表里的每一個函數設置了唯一的索引

然后調用指針所指向的函數~

這樣看來，調用虛函數與普通函數調用的效率相差無幾，只多出幾個指令。

虛函數真正的開銷與內聯函數有關~：在實際應用中，虛函數不應該被內聯，因為內聯意味著在編譯時刻用被調用函數的函數體來代替被調用函數。但是虛函數意味著運行時刻決定調用哪個一函數，so~~~虛函數付出的第三個代價啊：~不能內聯（通過對象調用虛函數的時候，這些虛函數可以內聯，但是大多數虛函數通過指針或者以用來調用的）。

~多重繼承的情況

多重繼承一般要求虛基類。沒有虛基類，如果一個派生類具有多個通向基類的繼承路徑，基類的數據成員會被復制到每一個繼承類對象里，繼承類與基類間的每一條路徑都有一個拷貝。

有了虛基類，通常使用指向虛基類的指針作為避免重復的手段，這樣需要在對象內部嵌入一個或者多個指針~也帶來了一定的開銷~

例如菱形繼承 ：

class A{};

class B:virtual public A{};

class C:virtual public A{};

class D:public B,public C{};

這里A是一個虛基類，因為B和C虛擬繼承了他。

對象 D 的布局：

B data

vptr

pointer to virtual base class

C data

vptr

pointer to virtual base class

D data members

A data members

vptr

上面四個類，只有三個vptr，因為B和D可以共享一個vptr  （為啥？）

現在我們已經看到虛函數如何使對象變得更大，以及為何不能把它內聯了~

下面我們看看RTTI的開銷 runtime type identifycation 所需要的開銷

通過rtti我們可以知道對象和類的有關信息，所以肯定在某個地方存儲了這些供我們查詢的信息，這些信息被存儲在type_info 類型的對象里，你可以通過typeid運算符訪問一個類的type_info對象。

每個類僅僅需要一個RTTI的拷貝，規范上只保證提供哪些至少有一個虛函數的對象的準確的動態類型信息~

why？和虛函數有啥關系~ 因為rtti設計在vtbl里

vtbl的下標0包含指向type_info對象的指針。所以使用這種實現方法，消費的空間是vtbl中占用一個額外的單元再加上存儲type_info對象所需要的空間。

------------------------罪惡的結束線 OVER~------------------------------------------

解決項目的問題，意識到斷言的重要性。如果一個程序在某處遇到了非法的值，那么最好的情況便是在此刻停下報錯，最壞的情況便是程序不吭不響的執行著~~直到你發現他執行的方式極為詭異，此時，你要花九牛二虎之力才能找到錯誤所在之處~~~~

學習一下斷言吧：

·······什么是斷言

在某處判斷某一個表達式的值為真或者假，如果假則輸出錯誤消息并停止程序的執行~

assert是宏，而不是函數，只在debug版本中有效，因此無需在release版本刪除。

·······哪幾種斷言

MFC

ASSERT

void foo(char* p,int size)
{
ASSERT(p != 0); // 驗證緩沖區指針
ASSERT((size >= 100); // 確認緩沖區大小至少為100字節
// foo 函數的其它計算過程
}
如果沒有定義_DEBUG預處理符，則該語句不會真正生成代碼。Visual C++會在調試模式編譯時自動定義_DEBUG，而在發行模式下，該預處理符是不存在的。如果定義了_DEBUG，則上述兩個斷言生成的代碼類如：
//ASSERT(p != 0);
do
{
if(!(p != 0) && AfxAssertFailedLine(__FILE__, __LINE__))
AfxDebugBreak();
} while(0);
//ASSERT((size >= 100);
do
{
if(!(size >= 100) && AfxAssertFailedLine(__FILE__,__LINE__))
AfxDebugBreak();
}while(0);

ASSERT_KINDOF(classname,pObject); ASSERT_KINDOF(CDocument,pDocument);

檢驗pObject指向的對象是classname類的一個對象或者其派生類的對象

ASSERT_VALID(pObject); pObject 必須是一個派生于CObject類的類對象，會調用其重寫的AssertValid函數 ，例如

如果使用應用向導或類向導生成基于MFC的類，通常會得到AssertValid()的骨架，最好改寫這些骨架代碼以增加最基本的完整性檢查。下面是一個典型的例子，類Sample從CObject繼承，假定它含有職員名字及其薪水：
class Sample : public CObject
{
    protected:
    CString m_Name; // 職員名字
    double m_Salary; // 薪水
public:
    Sample(LPCTSTR name,double salary) : m_Name(name), m_Salary(salary) {}
   #ifdef _DEBUG
        virtual void AssertValid() const;
    #endif
};
#ifdef _DEBUG
void Sample::AssertValid() const
{
    CObject::AssertValid(); // 驗證基類
    ASSERT(!m_Name.IsEmpty()); // 驗證職員名字
    ASSERT(m_Salary > 0); // 驗證薪水
}
#endif

CRT assertion

_ASSERT 和  _ASSERTE 后一個會在出錯時同時打印出條件判斷句

ANSI

assert()

注意：assert用于檢測非法的輸入，但是合法的輸入并不一定是正確的，例如：

int pB = (int*)malloc(sizeof(int)*1000);

assert(pB!=NULL) //錯誤的使用assert 他會在release版本失效~也就是說assert不應該對程序產生副作用

正確的做法：

int pB = (int*) malloc(sizeof(int)*1000);

if(pB == NULL)

{
   //錯誤處理

}

else{

}

另一個例子：

void draw(){

   CFigure* pF = getCF();

   assert(pf!=NULL);

   if(pf == NULL){}

   else{

   }

}

此處，對于getCF來說返回值為NULL是非法的，如果他的返回值可能為null就沒必要加上assert語句。

而下面的if語句則是為了防止release版本出現null指針的情況。

VERIFY()

由于ASSERT僅在程序的調試版起作用，測試表達式總是被動的。也就是說，它們不能包含賦值、增量、減量等真正改變數據的操作。但有時候我們需要驗證一個主動表達式，比如賦值語句。這時可以使用VERIFY代替ASSERT。下面是一個例子：
void foo(char* p,int size)
{
char* q; // 指針的副本
VERIFY(q = p); // 拷貝指針并執行驗證
ASSERT((size >= 100); // 確保緩沖區大小至少為100字節
// 執行 foo 的其它操作
}
在調試模式下ASSERT和VERIFY是相同的。但在release模式下，VERIFY能夠繼續對表達式求值（但不再進行斷言檢驗），而ASSERT語句在效果上就如同已經刪除了一樣。
盡管在MFC源代碼中可以找到一些應用VERIFY的例子，但ASSERT用得更為普遍。一些程序員總是完全避免使用VERIFY，因為他們已經習慣于使用被動斷言。請記住，如果在ASSERT語句中使用了主動表達式，編譯器不會發出任何警告。在發行模式下編譯時該表達式會被直接刪除，從而導致程序運行的錯誤。由于發行版程序不含調試信息，這種類型的錯誤是很難找到原因的。

項目中遇到了 RTTI 先學一部分 c++ primer內容

1. 運行時類型識別：

程序可以使用基類的指針或者引用來檢索這些指針或引用所指對象的實際派生類型

標準庫提供了兩個操作符：

1. typeid    他可以返回指針或者引用所指向對象的實際類型

2. dynamic_cast  將基類類型的指針或引用安全的轉為派生類的指針或者引用                            

對于不帶虛函數的類在編譯時期執行，否則在運行期間執行

使用時機：

基類指針調用派生類成員函數的話，一般應使用虛函數，這樣編譯器會根據對象的實際類型來選擇正確的函數。但是某些情況下無法使用虛函數，那么此

時如果需要使用基類指針調用派生類成員函數便需要使用RTTI強制轉換，而且必須檢查轉換是否成功了

(一) Dynamic_cast

dynamic_cast 如果轉換到指針失敗則返回 0 如果轉換到引用類型失敗則拋出 bad_cast 異常

對指針操作：

if(Derived *derivedPtr = dynamic_cast<Derived*> (basePtr)){

    //basePtr point to a derived object;

}else{

   //basePtr point to a base object;

}

在 if 語句中進行檢查 1.條件代碼內部知道 derivedPtr 的類型 2.不可能在測試代碼和使用代碼中加入代碼，也就是說不會在沒有測試前就使用derivedPtr 3.如果失敗外部不會使用未綁定的指針derivedPtr

對引用操作：

因為不存在空引用所以轉換失敗拋出異常

void f(const Base& b){

    try{

        const Derived &d = dynamic_cast<const Derived&> (b);

    }catch(bad_cast){

    }

}

(二) typeid

typeid(e) e是任意的表達式或者類型名

Base *bp;

Derived *dp;

//compare type at run time of two objects

if(typeid(*bp)==typeid(*dp)){

    //bp dp point to objects of the same type

}

if(typeid(*bp)==typeid(Derived)){

    //bp actually point to a Derived

}

注意typeid 測試的是 *bp 對象

//test always fails: The type of bp if pointer to Base

if(typeid(bp)==typeid(Derived)){

}

Base* 將永遠和Derived類型不同

只有typeid 的操作數是帶虛函數的類的對象的時候，才返回動態類型信息，測試指針返回指針的靜態的，編譯時類型

（三 ）type_info 類

作為typeid的返回值 提供

t1==t2 t1!=t2 t.name() 的操作

作為應用例子，可以實現一個類型敏感的相等操作符

friend bool operator == (const base& lhs, const base& rhs){

    return typeid(lhs)==typeid(rhs) && lhs.equal(rhs);

}

這樣可以處理基類子類混合的相等判斷了

STATE 模式：

一個對象的行為取決于他的狀態，而且它必須在運行時根據狀態改變他的行為。常規實現中，一個操作含有龐大的多分支的條件語句，且這些分支依賴于該對象的狀態。這個狀態通常使用一個或者多個枚舉常量表示。STate模式把這些狀態時候的對象看做一個獨立的對象，也就是將不同狀態時的行為分散到相應的狀態類中。要達到這樣的效果，需要context，也就是狀態的持有者，即原先的類；抽象狀態類，他封裝了與context交互的接口；具體狀態類，也就是一個個的具體狀態。context中保存一個抽象狀態類對象為成員，并delegate對象行為給他，從而使相應狀態下的行為代碼生效。如果狀態改變的準則不是固定的則state狀態類同時應該重寫changestate類以控制狀態的改變，否則可以在context中實現。

具體到我們的項目：

每一個device即為context，他擁有一個state對象，device中的函數processMsg(){state->processMSg();} 由于狀態改變的規則依賴于收到的消息，也就是說一個狀態可能轉換到多個狀態device的每個狀態需要重寫statechange方法，stateChange(){state->stateChange(this，msg);} 這樣，不同的狀態下的行為實現在具體狀態的類中，比原先的版本清晰明了，可讀性更強。

tchs-1 none 1000pt DFS 利用進入的方向劃分四個邊

tchs-2 250pt 直接算就行 我寫了2分 500pt 暴力可以過，但是判斷時候不能用stringstream 用算術判斷 也可以用構造法 1000pt 每一位有三種可能性

           不用，保持不動，變化，分別遞歸計算value并更新結果即可，由于遞歸深度最多只有13層所以不會tle

           另外也可以寫出基數為3的循環來遍歷每一種情況具體看代碼

    for(i=0,A[0]++;A[i]>2;i++){
       A[i]=0;A[i+1]++;
  }

tchs-3 1000pt 要想使乘積最大，需要更多的3即可 500pt 又看錯題了 ~~~ft 要注意題目一定要看清楚

tchs-4 500pt 模擬題，好難懂 音樂的~ 可以都乘以16 用整數來計算 浮點會很煩~ 這種題思路要清晰 一步一步來

tchs-5 250pt 簡單題，注意使用double 可以用1.0*int就不用double()了還有 int(h+1e-9);

          500pt 簡單題，把所有word提取出來然后排序，再依次插入標點即可，注意有些小技巧

思路要清晰，兩個輪替記錄即可

                1000pt    顯然的BFS 利用隊列 只是題意不太好理解，最好把判斷寫成小函數，主程序會看起來比較清晰，不容易出錯~ 一步一步來

silver組：

比賽那天感冒，第一題就弄暈了，現在題解出來了，補上吧~~

暫時只有第一題的：

Problem 6: Bobsledding [Brian Jacokes, 2009]

Bessie has entered a bobsled competition because she hopes her hefty
weight will give her an advantage over the L meter course (2 <= L
<= 1,000,000,000).

Bessie will push off the starting line at 1 meter per second, but
her speed can change while she rides along the course. Near the
middle of every meter Bessie travels, she can change her speed
either by using gravity to accelerate by one meter per second or
by braking to stay at the same speed or decrease her speed by one
meter per second.

Naturally, Bessie must negotiate N (1 <= N <= 100,000) turns on the
way down the hill. Turn i is located T_i meters from the course
start (1 <= T_i <= L-1), and she must be enter the corner meter at
a speed of at most S_i meters per second (1 <= S_i <= 1,000,000,000).
Bessie can cross the finish line at any speed she likes.

Help Bessie learn the fastest speed she can attain without exceeding
the speed limits on the turns.

Consider this course with the meter markers as integers and the
turn speed limits in brackets (e.g., '[3]'):

|   1   2   3   4   5   6   7[3]
|---+---+---+---+---+---+---+
|                            \
Start                         + 8    
                               \
                                + 9    
                                 \
                                  + 10       +++ 14 (finish)
                                   \         /
                              11[1] +---+---+
                                        12  13[8]

Below is a chart of Bessie's speeds at the beginning of each meter length
of the course:

Max:                              3               1       8
Mtrs: 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14 
Spd:  1   2   3   4   5   5   4   3   4   3   2   1   2   3   4

Her maximum speed was 5 near the beginning of meter 4.

PROBLEM NAME: bobsled

INPUT FORMAT:

* Line 1: Two space-separated integers: L and N

* Lines 2..N+1: Line i+1 describes turn i with two space-separated
        integers: T_i and S_i

SAMPLE INPUT (file bobsled.in):

14 3
7 3
11 1
13 8

OUTPUT FORMAT:

* Line 1: A single integer, representing the maximum speed which
        Bessie can attain between the start and the finish line,
        inclusive.

SAMPLE OUTPUT (file bobsled.out):

5

題目看起來挺復雜，其實主要是求出各個turn處的最大速度，分析得到每個turn的最大速度需要滿足三個條件， M_i = min (S_i , t_i – t_{i-1} + M_{i-1} , S_k + t_k – t_i [for all k > i ] )

因此處理每一個turn都要查詢N個turn N*N的復雜度顯然對于大數據要TLE的

逆向思考，如果我們反過來考慮，對于每一個之后的turn來說 如：i  如果他最大速度為 m_i

那么 在turn i-1處，他不能超過的最大速度 m_{i-1} = min(S_i,m_i+t_i – t_{i-1});這樣成功的把后面兩個限制轉換為逆推的結果而不是向后查詢

剩下的問題便是如果知道兩個turn之間距離，以及turn的速度最大值，如何求出之間的最大值，畫圖顯然可以得到一種算式 maxspeed = min(s1,s2) + (dist2-dist1+abs(s1-s2))/2;

或者 maxspeed = max(s1,s2) + (dist2 – dist1 – abs(s1-s2))/2;

注意在開頭和結尾加入虛擬的turn就可以了

----------------------------------------------3個月后的修改線-----------------------------------------------------------------

第一個復習周末 ，先看的這道題，過了這么久果然又杯具的不會了~~之前的解釋寫的有些模糊。

首先，如果要想達到最快速度，那么只需要求得每個turn 能夠達到的最快速度即可~

所以題目編程求每個turn能達到的最快速度了。首先得到簡單的式子，也就是上面的min{1,2,3}，第一個條件決定在這個turn我們可以加速達到的最大速度，后兩個條件為了防止滑的過快，減不下來不能通過自己以及以后的turn。按這種算法，我們必須對每一個turn遍歷之后的turn，很沒有效率。后面兩個條件是為了防止在turn處滑的過快~~那么每一個m_i 只需要滿足 min(S_i,m_{i+1}+t[i+1]-t[i]);只要這樣，就可以保證雪橇可以減速以通過下一個turn。顯然最后一個turn的 m_i 就是他的s_i，這樣遞推回去就能得到一組slowdown值，然后利用前面的式子 up[i]=min{m_i[i],up[i-1]+lenth};正向推回去就可以得到每一個turn的maxspeed。至于最大speed的算法上面已經給出了~

------------------希望下次可以直接做出來，不要再忘了。。。。-------------