本文共 2291 字，大约阅读时间需要 7 分钟。

题目

例 2.3 日期差值 （九度教程第 6 题）

时间限制：1 秒 内存限制：32 兆 特殊判题：否

题目描述：

有两个日期，求两个日期之间的天数，如果两个日期是连续的我们规定他们 之间的天数为两天 输入： 有多组数据，每组数据有两行，分别表示两个日期，形式为 YYYYMMDD 输出： 每组数据输出一行，即日期差值 样例输入： 20110412 20110422 样例输出： 11 来源： 2009 年上海交通大学计算机研究生机试真题

思路

把问题统一到特定日期与一个原点时间（如 0000 年 1 月 1 日）

的天数差，当要求两个特定的日期之间的天数差时，我们只要将它们与原点日期 的天数差相减，便能得到这两个特定日期之间的天数差（必要时加绝对值）。这 样做有一个巨大的好处——预处理。我们可以在程序真正开始处理输入数据之 前，预处理出所有日期与原点日期之间的天数差并保存起来。当数据真正开始输 入时，我们只需要用 O（1）的时间复杂度将保存的数据读出，稍加处理便能得 到答案。值得一提的是，预处理也是空间换时间的重要手段（保存预处理所得数 据所需的内存来换取实时处理所需要的时间消耗）。

代码

#include
   
    #define ISLEAPYEAR(x) x % 100 != 0 && x % 4 == 0 || x % 400 == 0 ? 1 : 0 //简洁写法 using namespace std;int DaysOfMonth(int month, int year){    switch(month)    {        case 1: case 3: case 5: case 7: case 8: case 10: case 12:            return 31;             break;        case 4: case 6: case 9: case 11:            return 30;             break;        case 2:            if(ISLEAPYEAR(year)) return 29;        else return 28;    }}class Date //注意不要加括号 {    public:        int year;        int month;        int day;        Date() //初始化日期为0/1/1 作为基准         {            year = 0;            month = 1;             day = 1;        }        void update() //将日期加一天         {            day++;            if(day > DaysOfMonth(month, year))            {                day = 1;                month ++;                if(month > 12)                {                    month = 1;                    year ++;                }            }        }};int Abs(int x){    return (x >= 0 ? x : -1*x); }int buf[6001][13][32]; //用来存储每个日期与基准日期的差值 int main(){    Date temp;    int count = 0;    while(temp.year < 6000)    {        buf[temp.year][temp.month][temp.day] = count;        temp.update();        count ++;    }    int y1, m1, d1, y2, m2, d2;    while(scanf("%4d%2d%2d", &y1, &m1, &d1) != EOF) //此处注意对于格式的控制     {        scanf("%4d%2d%2d", &y2, &m2, &d2);        cout << Abs(buf[y2][m2][d2] - buf[y1][m1][d1] + 1) << endl;    }    return 0;}
   

总结

1. 类名不要加括号
2. 注意此题以空间换时间的思想
3. 注意此题的宏定义函数写法
4. 对于输入格式的控制%4d
5. 在保存某个特定日期与原点日期的天数差时，我们使用了三维数组，用年、月、日分别表示该数组下标，这便将日期本身与其存储地址联系了起来
6. 我们将 buf[5001][13][32]这个相对比较耗费内存的数组定义成**全局变
   量，**这不是偶然的。由于需要耗费大量的内存，若在 main 函数（其它函数也一样）之中定义该数组，其函数所可以使用的栈空间将不足以提供如此庞大的内存出现栈溢出，导致程序异常终止。所以，今后凡是涉及此类需要开辟大量内存空间的情况，我们都必须在函数体外定义，即定义为全局变量。或者在函数中使用malloc等函数动态申请变量空间。读者必须牢记这一点。

转载地址：http://ikuin.baihongyu.com/