乱八七糟的代码

第四章  效率

······条款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的算法上面已经给出了~

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