关于时间复杂度

代码时间复杂度应在百万级别，即若算法的时间复杂度是O(n^2)，则该n（往往在题目中会给出数据范围）不应大于3000，否则将会达到我们所说的千万数量级复杂度，从而程序运行时间超出题目中给出的用时限定。举例来说，我们不能在1秒时限的题目当中对10000个整数进行冒泡排序，而必须使用快速排序等时间复杂度为O(nlogn)的排序算法，否则程序很可能将会得到运行时间超出限制的评判结果。

第二章 经典入门

排序

scanf

while (scanf ("%d",&n) != EOF) ，它在完成输入n的同时又完成了什么看起来令人迷惑的条件判断？要回答这个问题，我们首先要明确两点：
第一，scanf函数是有返回值的（尽管大多时候都会被人忽略），它将返回被输入函数成功赋值的变量个数。在此例中，若成功完成输入并对n赋值，scanf函数的返回值即为1。我们即是通过该返回值来完成循环条件的判断的。
第二，我们也要注意到，该例题面中明确了输入数据会有多组，我们将要对每组输入都输出相应答案。并且，事先我们并不知道将会有多少组数据被输入到程序中。
于是，我们可以使用该循环测试条件来完成对输入是否结束的判断。过程如下：
如仍有测试数据未被测试完，那么该组测试的开头一行将如题面所说，为一个整数（n），其将会被scanf语句赋值给变量n，那么scanf返回值为1，不等于EOF（-1），循环条件成立，程序进入循环体，执行程序；
如果输入已经到达结尾（输入文件到达末尾或在命令台输入中输入Ctrl+z），scanf函数无法再为变量n赋值，于是scanf函数返回EOF（end of file）。至此，循环条件不成立，程序跳过循环体，执行return 0，使程序正常的结束。该循环判断条件既保证了可以对多组测试数据进行计算，同时又使程序在输入结束后能够正常的退出。反之，如果我们不使用循环，程序在处理完一组数据后就会退出，后续测试数据无法被正常的处理。但若我们使用死循环而不加以任何退出条件，那么程序在处理完所有的测试数据后仍就不能正常的退出，虽然程序已经输出了所有测试数据的答案，但评判系统还是会认为程序在限制时间内无法运行完毕，于是返回超时的评判结果。正因为如此，初学者很容易因为这个原因，出现莫名其妙的程序超时。所以，我们必须使用该循环判断条件来完成以上两个功能。
值得一提的是，若输入为字符串而程序采用gets（）的方法读入，则相同功能的循环判断语句为while(gets(字符串变量))。

排序

若冒泡排序的数据复杂度太大，则可以使用c++的快速排序函数sort()
在头文件方面包含了algorithm头文件，并使用using namespace std语句声明了我们将会使用标准命名空间（sort被定义在其中）。此例中，sort函数的两个参数代表待排序内存的起始地址和结束地址（sort函数还有另外的重载形式，在后文中会有所提及），在此例中起始地址为buf，结束地址为buf + n。该函数调用完成后，buf数组中的数字就已经通过快速排序升序排列。我们只需对其输出即可。

#include <stdio.h>
#include <algorithm>
using namespace std;
    sort    (buf,buf + n); //使用该重载形式,表明将要使用自己定义的排列规则

假如我们将要对给定的数组进行降序排列该如何操作

#include <stdio.h>
#include <algorithm>
using namespace std; 
bool cmp (int x,int y) 
{ //定义排序规则 
    return x > y; 
    } 
int main () 
{  
    int n;   
    int buf[100];  
    sort    (buf,buf + n,cmp); //使用该重载形式,我们表明将要使用自己定义的排列规则
    }

如该代码所示，我们新定义了一个cmp函数，来实现对于新的排序规则的定义。关于cmp函数的定义规则我们只需简单的记得，当cmp的返回值为true时，即表示cmp函数的第一个参数将会排在第二个参数之前（即在我们定义的规则中，cmp表示第一个参数是否比第二个参数大，若是，则排在前面）。为了实现降序排列，我们只要判断两个参数的大小，当第一个参数比第二个参数大时返回true。然后，只需要调用sort函数的另一种重载方式：sort（排序起始地址，排序
结束地址，比较函数），如代码所示，我们便完成了对我们给定的内存区间的降序排列。

对一些由基本类型组成的结构体进行排序。

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std; 
struct E {
    char name[101];
    int age;  
    int score; 
    }buf[1000]; 
bool cmp(E a,E b) { 
    //实现比较规则 
    if (  a.score != b.score) 
        return a.score < b.score;  
        //若分数不相同则分数低者在前
    int tmp = strcmp(a.name,b.name);  
    if (tmp != 0) 
        return tmp < 0; 
        //若分数相同则名字字典序小者在前 
    else 
        return a.age < b.age; //若名字也相同则年龄小者在前
    }
int main () 
{  
    int n;  
    while (scanf ("%d",&n) != EOF) 
    { 
        for (int i = 0;i < n;i ++) 
        {
            scanf ("%s%d%d",buf[i].name,&buf[i].age,&buf[i].score);
        }    // 输入
        sort(buf,buf + n,cmp); //利用自己定义的规则对数组进行排序
    }
    return 0；
}  

同样的，与编写cmp类似，我们也可以直接定义该结构体的小于运算符来说明排序规则。

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std; 
struct E {  
    char name[101];  
    int age;  
    int score;  
    bool operator < (const E &b  ) const { //利用C++算符重载直接定义小于运算符
        if (score != b.score) 
            return score < b.score; 
        int tmp = strcmp(name,b.name); 
        if (tmp != 0) 
            return tmp < 0; 
        else return age < b.age;  
        } 
}buf[1000]
int main () {  
    int n;
    while (scanf ("%d",&n) != EOF) { 
         for (int i = 0;i < n;i ++) {    
             scanf("%s%d%d",buf[i].name,&buf[i].age,&buf[i].score);     
         }    
         sort(buf,buf + n);  
         for (int i = 0;i < n;i ++) { 
             printf ("%s %d %d\n",buf[i].name,buf[i].age,buf[i].score);    
         }     
         }  
     return 0; 
} 

由于已经指明了结构体的小于运算符，计算机便知道了该结构体的定序规则（sort函数只利用小于运算符来定序，小者在前）。于是，我们在调用sort时，便不必特别指明排序规则（即不使用第三个参数），只需说明排序起始位置和结束位置即可。虽然，该方法与定义cmp函数的方法类似，我个人还是建议使用第二种方法。这样，首先可以对重载算符的写法有一定的了解；其次，在今后使用标准模板库时，该写法也有一定的用处。后文中，将会广泛使用该方法编写例程。若读者坚持使用定义cmp函数的写法，只需自行将重载小于运算符中的语句转化为定义cmp函数函数体的相关语句即可，并在调用sort函数时加上第三个参数cmp