链接: http://poj.grids.cn/practice/2797/

这题乍看之下确实没什么思路,后面终于明白题意了,然后突然想到可以用字典树做,速度当然会是非常快的…
但是其实还有一种更简单的方法,那就是对所有字符串排序之后,每个字符串的前缀长度其实就是由其前一个和后一个字符串共同决定,
nLen = max(nOne, nTwo), nOne 和 nTwo就分别代表当前字符串和前后字符串公告部分的长度+1后的值…
代码写出来写非常简单…同学这样实现了下,也轻松过了…

然后我就辛苦的写了一棵字典树…可能我的写法不是很标准,因为我没参考什么模板,自己硬想出来怎么写的…
我的想法是开一个静态大数组,第一个结点作为根,不存储数据,从第二个结点开始作为自由空间分配…
其实,就是对26颗字典树虚拟了个无数据的根结点…
使用了虚拟的根结点后,代码比用26个根结点简洁很多…
刚开始我就假设1-26号结点分别为a-z,作为26颗树的根,
而且下26个结点的位置我用的是索引,没用指针,后面换成了指针,代码看起来更舒服了…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <string.h>
#define LETTER_NUM 26
#define WORD_LEN_MAX 25
#define WORD_NUM_MAX 1030
#define NODE_MAX (WORD_LEN_MAX * WORD_NUM_MAX + 10)
struct WORD_TREE
{
char ch;
WORD_TREE* next[LETTER_NUM];
int nTime;
};
WORD_TREE tree[NODE_MAX];
WORD_TREE* pFreeNode = tree + 1;//第一个结点作为头结点,不存储数据
char szWords[WORD_NUM_MAX][WORD_LEN_MAX];
void AddToTree(char* pszStr)
{
WORD_TREE* pTree = tree;
while (*pszStr && pTree->next[*pszStr - 'a'])
{
pTree = pTree->next[*pszStr - 'a'];
pTree->nTime++;
++pszStr;
}
while (*pszStr)
{
pFreeNode->ch = *pszStr;
pFreeNode->nTime++;
pTree->next[*pszStr - 'a'] = pFreeNode;
pTree = pFreeNode;
++pszStr;
++pFreeNode;
}
}
int FindPrefix(char* pszStr)
{
WORD_TREE* pTree = tree;
int nLen = 0;
while (*pszStr)
{
++nLen;
pTree = pTree->next[*pszStr - 'a'];
if (pTree->nTime <= 1)
{
break;
}
++pszStr;
}
return nLen;
}
int main()
{
int nCount = 0;
while (scanf("%s", szWords[nCount]) != EOF)
{
AddToTree(szWords[nCount]);
nCount++;
}
for (int i = 0; i < nCount; ++i)
{
int nLen = FindPrefix(szWords[i]);
printf("%s ", szWords[i]);
for (int j = 0; j < nLen; ++j)
{
putchar(szWords[i][j]);
}
putchar('\n');
}
return 0;
}

链接:[http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1207]

问题描述是:给定一个大于0的整数N(1<=N<=10^8),判断其是否可能是一个直角三角形的直角边(这个三角形的三条边必须都是整数)…
这个题还是做得我挺郁闷的。。。刚开始完全没思路。。。后面没办法,硬着头皮往下想。
对于勾股定理a^2 + b^2 = c^2,假设N是a,可以得到a^2 = (c + b) * (c -b), 那么(c + b)和(c - b)是a^2的2个因子,而且(c+b)>=a,(c-b)<=a。。。
到这一步已经可以用程序轻松解决出来了,但是对于任意一个整数N来说,其复杂度都是O(N),那么计算量还是很大的…
这个时候只需要枚举1-N,求出a^2的2个因子,然后求c和b,如果能得出c和b都是正整数那么,就满足条件了…
但是这样还是过不了题,因为数据量不会这么小…数据量好像有10000组。。。
那么还需要推导出进一步的结论…
因为1和a^2一定是a^2的一对因子,那么(c+b) = a^2和(c-b) = 1一定可以成功,
则可以推导出,2 c = a^2 + 1。
要c可解,a必须为奇数,那么可以推导出如果a是奇数,一定是直角边了。。。
如果a是偶数了,可以化简为 4
(a / 2) ^ 2 = 4 (c + b) \ (c - b) = (2c + 2b) * (2c - 2b) = a ^ 2,那么继续推导也可以得到一样的结果了…

结论就是:对于大于等于3的正整数都可以是一条直角边(>=3也可以根据上面的c和b是正整数推导出来)…

链接: http://poj.grids.cn/practice/2820
链接: http://poj.grids.cn/practice/2801

为啥把这2个不相干的题目放在一起了…说实话这其实也是二个容易的题目,尤其第二个更容易想到…第一个也许暂时
没那么容易想出来。。。
而且感觉第一个古代密码还挺有意思的…判断一个字符串是否能够通过移位和替换方法加密成另外一个字符串。。。
至于第二个,各位去看看题目吧。。。
也是个解法跟题目不大相关的题目。。。
这2个题最大的特点和共同点就是解法和题目意思想去甚远。。。
所以我觉得做这种二丈和尚摸不早头脑的题,思维应该往跟题意背离的方向思考。。。

尤其第一个题,如果只看代码,即使代码可读性再好,也不知道代码有何意义,有何目的,跟题意有啥关系。。。
不过第一个居然轻松AC了,虽然我2b得搞了个ce和re出来了…
第一个的转换方法是,计算出现的字符’A’-‘Z’的出现次数,然后从大小排序,如果针对加密后的字符串得到的结果一直大于等于
加密前的字符串得到的结果,表明答案是YES…具体还是看代码吧…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <string.h>
#include <algorithm>

using std::sort;
bool Greater(int one, int two)
{
return one > two;
}

int main()
{
char szOne[110];
char szTwo[110];
int nNumOne[26];
int nNumTwo[26];

while (scanf("%s%s", szOne, szTwo) == 2)
{
memset(nNumOne, 0, sizeof(int) * 26);
memset(nNumTwo, 0, sizeof(int) * 26);

char* psz = szOne;
while (*psz)
{
++nNumOne[*psz - 'A'];
++psz;
}
psz = szTwo;
while (*psz)
{
++nNumTwo[*psz - 'A'];
++psz;
}
sort(nNumOne, nNumOne + 26, Greater);
sort(nNumTwo, nNumTwo + 26, Greater);
bool bIsYes = true;
for (int i = 0; i < 26; ++i)
{
if (nNumOne[i] < nNumTwo[i])
{
bIsYes = false;
break;
}
}
if (bIsYes)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}

return 0;
}

链接: http://poj.grids.cn/practice/2804/

这也是一个很简单的题目,大家一看都知道用什么方法了,当然如果是查找的话,顺序查找是不行的,
方法一,是用map,建立个map的字典,注意不要想当然用map,
那样得动态分配内存,或者还是先开个大数组存好字典,其结果还是多浪费了内存…
排序+二分也不错的,因为数据量确实很大,而且题目也建议用c的io输入,所以这样再建立map
中间还得转换一下…
总之做这个题还是很顺利的,就wa了一次,原因是2分写错了,我也很久没在oj上写2分了…

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <string.h>
#include <algorithm>

#define MAX_WORD_LEN 11
#define MAX_DICTION_ITEM (100000 + 10)

using std::sort;

struct Dictionary
{
char szWord[MAX_WORD_LEN];
char szEnglish[MAX_WORD_LEN];
};

Dictionary diction[MAX_DICTION_ITEM];

bool CmpDictionItem(Dictionary one, Dictionary two)
{
return strcmp(one.szWord, two.szWord) < 0;
}

int FindEnglish(char* pszWord, int nItemNum)
{
int nBeg = 0, nEnd = nItemNum - 1;
int nCmp = 0;

while (nBeg <= nEnd)
{
int nMid = (nBeg + nEnd) / 2;
nCmp = strcmp(pszWord, diction[nMid].szWord);
if (nCmp == 0)
{
return nMid;
}
else if (nCmp < 0)
{
nEnd = nMid - 1;
}
else
{
nBeg = nMid + 1;
}
}

return -1;
}

int main()
{
char szStr[30];
char szWord[MAX_WORD_LEN];
int nCount = 0;
int nAnsItem = 0;

while (fgets(szStr, 29, stdin), szStr[0] != '\n')
{
sscanf(szStr, "%s%s", diction[nCount].szEnglish, diction[nCount].szWord);
++nCount;
}
sort(diction, diction + nCount, CmpDictionItem);
while (scanf("%s", szWord) == 1)
{
if ((nAnsItem = FindEnglish(szWord, nCount)) != -1)
{
printf("%s\n", diction[nAnsItem].szEnglish);
}
else
{
printf("eh\n");
}
}

return 0;
}

其实我的主要目的是为了指出二分的写法,大家看我的FindEnglish函数,传递的是数组的地址和数组的长度,
然后我写函数体的时候用的是[]的形式,就是下确界,上确界,这样最重要的是需要考虑循环的条件是<还是
<=,其实这也很好判断,因为上界和下界都能够取到,所以=是成立的…而且修改right的时候,必须将right = mid - 1,
原因也是因为这是上确界,
但是如果是上不确界了,那么等号就必须去掉,而且right也只能修改为mid,因为mid-1就是确界了,而mid才是上不确界…
想到这个程度的话,以后写只有唯一解二分就应该不会出错了…但是写查找满足条件的最大或者最小解的二分还需要其它技巧…

链接: [http://poj.grids.cn/practice/2964/]

这本来就是一个简单的题目,但是还是值得我用一篇文章的位置。大家都做过闰年的题目,这只是闰年的一个升级版。。。本来我不至于这么纠结这个题目的,一看到题目,
我就考虑到了一次次减去天数来加年数和月份,而且我还想在读入数据之前初始化一个存储2000-9999年每年有多少天得数组…这样就可以避免循环时候计算每年的天数了…但是我还是怕时间不够,所以我想到了个O(1)的算法…
那就是按照题目的说明,其实每400是一个周期的,但是我前面写代码的时候把4年当中一个小周期,100年当中一个中周期,400年当中一个大周期,同样的处理了…
事实上,只能对400作为周期处理,其它的必须分类讨论,虽然代码写出来很复杂,而且我也因为出现这个bug错了无数次,但是我还是感觉非常值得的…因为这是我独立思考的成果,耗费了多少时间和精力倒是无所谓…写算法题,目的不仅仅应该是学习了多少个算法,而是在于能力的提高,个人的严谨性,思考问题的完整性等等…一直觉得自己思考问题时候有创意,但是完整性和严谨性很低…

下面贴我的代码吧,只用了10ms,如果采用第一种方法则需要60ms-70ms…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdio.h>

#define SMALL (365 * 3 + 366)
#define MID (SMALL * 25 - 1)
#define BIG (MID * 4 + 1)

char* pszWeekdays[7] =
{
"Saturday", "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"
};

int nDaysOfMon[2][13] =
{
{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};

void GetMonthAndDay(int nDays, bool bIsLeap, int* nMon, int* nDay)
{
int nChoose = 0;
int i = 0;

if (bIsLeap)
{
nChoose = 1;
}
*nMon = *nDay = 0;
i = 1;
while (nDays > nDaysOfMon[nChoose][i])
{
nDays -= nDaysOfMon[nChoose][i];
++i;
}
*nMon = i;
*nDay = nDays;
}

void CountSmall(int* pnDays, int* pnPastYears, int* pnMon, int* pnDay)
{
if (*pnDays >= 3 * 365)//4
{
*pnPastYears += 3;
*pnDays -= 365 * 3;
GetMonthAndDay(*pnDays + 1, true, pnMon, pnDay);
}
else//1-3
{
*pnPastYears += *pnDays / 365;
*pnDays %= 365;
GetMonthAndDay(*pnDays + 1, false, pnMon, pnDay);
}
}

int main()
{
int nPastDays = 0;
int nPastYears = 0;
int nYear = 0, nMon = 0, nDay = 0;

while (scanf("%d", &nPastDays), nPastDays != -1)
{
int nTemp = nPastDays;
nPastYears = 0;

if (nTemp < 366)
{
GetMonthAndDay(nTemp + 1, true, &nMon, &nDay);
nPastYears = 0;
}
else
{
nPastYears++;
nTemp -= 366;

nPastYears += (nTemp / BIG) * 400;
nTemp %= BIG;

if (nTemp >= MID * 3)//301-400年(以4为周期)
{
nTemp -= MID * 3;
nPastYears += 300;

nPastYears += nTemp / SMALL * 4;
nTemp %= SMALL;

CountSmall(&nTemp, &nPastYears, &nMon, &nDay);
}
else//1-300年
{
nPastYears += nTemp / MID * 100;
nTemp %= MID;

if (nTemp >= SMALL * 24)//97-100年(4个平年)
{
nTemp -= SMALL * 24;
nPastYears += 4 * 24;

nPastYears += nTemp / 365;
nTemp %= 365;
GetMonthAndDay(nTemp + 1, false, &nMon, &nDay);

}
else//1-96年
{
nPastYears += nTemp / SMALL * 4;
nTemp %= SMALL;

CountSmall(&nTemp, &nPastYears, &nMon, &nDay);
}
}
}
printf("%d-%02d-%02d %s\n", nPastYears + 2000, nMon, nDay, pszWeekdays[nPastDays % 7]);
}

return 0;
}

链接:http://poj.grids.cn/practice/2818
这其实就是一个简单的移位密码算法题,只是多了个循环而已,密码学里面也指出过循环运算是没有效果的,所以题目估计也就考察了这一点,如果没有找出循环周期,此题会一直超时的…
刚开始,我就直接模拟K次加密,显然超时了,当时还不信了,以为简单至此。。。
后面我就开始改进了,刚开始是把周期计算和加密放在一起写了,样例也过了,但是还是一直错…
没办法再改,我改成把周期求出来,再对加密次数K取模后,再进行运算…
好吧,还是一样wa,后面就变成PE了。。。
最后,这个题经过我近2个小时的奋战,终于过了,一共错了近10次吧…第一次提交是距现在1个多小时前了…
最后发现错误的原因还是换行输出的地方错了,题目要求是每一组中间有个空行,我则输出的是每次计算后有个空行…
实在无语…
思维不严谨啊…

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <string.h>
#define N_MAX 200 + 10
int main()
{
int nN = 0;
int nNArr[N_MAX];//密钥
int nK = 0;
char szMsg[N_MAX];
char szMsgBckup[N_MAX];//字符串备份
int nCir[N_MAX];//周期
int nMsgLen = 0;
int nPos = 0;
int i, j;

while (scanf("%d", &nN), nN != 0)
{
for (i = 1; i <= nN; ++i)
{
scanf("%d", &nNArr[i]);
}

for (i = 1; i <= nN; ++i)//计算周期
{
nPos = i;
for (j = 1; ; ++j)
{
nPos = nNArr[nPos];
if (nPos == i)
{
nCir[i] = j;
break;
}
}
}

while (scanf("%d", &nK), nK != 0)
{
getchar();//销掉空格
gets(szMsg + 1);
nMsgLen = strlen(szMsg + 1);
for (i = nMsgLen; i < nN; ++i)
{
szMsg[1 + i] = ' ';
}
szMsg[1 + nN] = '\0';
strcpy(szMsgBckup + 1, szMsg + 1);

for (i = 1; i <= nN; ++i)
{
nPos = i;
int nTimes = nK % nCir[i];
for (j = 1; j <= nTimes; ++j)
{
nPos = nNArr[nPos];
}
szMsg[nPos] = szMsgBckup[i];
}

printf("%s\n", szMsg + 1);
}
printf("\n");
}

return 0;
}

链接:http://poj.grids.cn/practice/1017
说实话
这就是个简单的装箱子问题,很容易想清楚装箱子的过程,而且这个过程是满足贪心算法的,
所以只需要用代码模拟整个装箱子的过程即可,但是这样真的就足够了吗???
我刚开始就是用代码模拟这个手动过程了,虽然AC了,但是代码有150行左右,逻辑也显得过于复杂了,
得不偿失。。。整个过程是66的一个占一个箱子,55的也必须一个占一个箱子,但是需要补11个11的,
4
4的也是一个占一个箱子,但是需要补5个22的,如果22的不足够,则用11的代替,
3
3的4个占一个箱子,但是会有余数,可能余下1,2,3个33的箱子,这个时候必须非情况考虑,
1个3
3的需要和5个22的,7个11的组合,2个33的需要和3个22的,6个11的组合,
3个3
3的需要和1个22的,5个11的组合,最后考虑9个22的装一个箱子,多余的22用11的去填充尽量挤满一个箱子,
最后36个1
1的装一个箱子,余下的1*1的也必须占一个箱子。。。
这个过程说出来已经非常复杂了,更何况用代码写,我费了九牛二虎之力才写出来,WA了一次才AC了…

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <stdio.h>
int main()
{
int one, two, three, four, five, six;
int num = 0;
while (scanf(“%d%d%d%d%d%d”, &one, &two, &three, &four, &five, &six) == 6)
{
if (one == 0 && two == 0 && three == 0 && four == 0 && five == 0 && six == 0)
{
break;
}
num = six;
num += five;
if (one > five * 11)
{
one -= five * 11;
}
else
{
one = 0;
}
num += four;
if (two > four * 5)
{
two -= four * 5;
}
else
{
if (one > four * 5 * 4 – two * 4)
{
one -= four * 5 * 4 – two * 4;
}
else
{
one = 0;
}
two = 0;
}
num += three / 4;
three = three % 4;
if (three == 1)
{
if (two > 5)
{
two -= 5;
if (one > 7)
{
one -= 7;
}
else
{
one = 0;
}
}
else
{
if (one > 27 – two * 4)
{
one -= 27 – two * 4;
}
else
{
one = 0;
}
two = 0;
}
++num;
}
if (three == 2)
{
if (two > 3)
{
two -= 3;
if (one > 6)
{
one -= 6;
}
else
{
one = 0;
}
}
else
{
if (one > 18 – two * 4)
{
one -= 18 – two * 4;
}
else
{
one = 0;
}
two = 0;
}
++num;
}
if (three == 3)
{
if (two > 1)
{
two -= 1;
if (one > 5)
{
one -= 5;
}
else
{
one = 0;
}
}
else
{
if (one > 9 – two * 4)
{
one -= 9 – two * 4;
}
else
{
one = 0;
}
two = 0;
}
++num;
}
num += two / 9;
two = two % 9;
if (two)
{
if (one > 36 – two * 4)
{
one -= 36 – two * 4;
}
else
{
one = 0;
}
++num;
}
num += one / 36;
if (one % 36)
{
++num;
}
printf(“%d\n”, num);
}
return 0;
}

这样的写法显然不好吧。。。首先,余下1,2,3个33时候需要填几个22的可以存储在数组里面,这样就可以不用写重复代码了,
如果再从整体考虑余下多少个格子,就不用用贪心算法模拟装箱子的过程了。。。
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
int main()
{
int one, two, three, four, five, six;
int num = 0;
int twoPlace[4] = {0, 5, 3, 1};
int remTwo, remOne;
while (scanf("%d%d%d%d%d%d", &one, &two, &three, &four, &five, &six) == 6)
{
if (one == 0 && two == 0 && three == 0 && four == 0 && five == 0 && six == 0)
{
break;
}
num = six + five + four + (three + 3) / 4;
remTwo = four * 5 + twoPlace[three % 4];
if (two > remTwo)
{
num += (two – remTwo + 8) / 9;
}
remOne = 36 * num – 36 * six – 25 * five – 16 * four – 9 * three – 4 * two;
if (one > remOne)
{
num += (one – remOne + 35) / 36;
}
printf(“%d\n”, num);
}
return 0;
}

链接:

http://poj.grids.cn/practice/2808

方法1(空间换时间):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>

int main()
{
int L, M;
int nTrees[10005] = {0};
int start, end;
int nCount = 0;

scanf("%d%d", &L, &M);
while (M--)
{
scanf("%d%d", &start, &end);
for (int i = start; i <= end; ++i)
{
nTrees[i] = 1;
}
}

for (int i = 0; i <= L; ++i)
{
if (nTrees[i] == 0)
{
nCount++;
}
}

printf("%d\n", nCount);
return 0;
}

方法2(合并区间):
思想是将所有区间存储在数组里面,对所有区间以下限为标准排序,然后从头至尾扫描区间数组,合并区间的方法是:当前区间初始化为第一个区间,然后判断下一个区间的下限是否已经超过当前区间的上限,如果是这样的话,就无法继续合并了,那么就继续已经合并区间的长度,重新开始一次新的合并,否则的话,将下一个区间合并到当前区间起来。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <stdlib.h>
#define M_MAX 100 + 2
struct Area
{
int start;
int end;
};
int CompareArea(const void *elem1, const void *elem2)
{
return ((Area*)elem1)->start - ((Area*)elem2)->start;
}
int main()
{
Area area[M_MAX], temp;
int L = 0;
int M = 0;
int count = 0;
scanf("%d%d", &L, &M);
for (int i = 0; i < M; ++i)
{
scanf("%d%d", &area[i].start, &area[i].end);
}
qsort(area, M, sizeof(Area), CompareArea);

temp = area[0];
for (int i = 1; i < M; ++i)
{
if (area[i].start <= temp.end)
{
if (area[i].end > temp.end)
{
temp.end = area[i].end;
}
}
else
{
count += temp.end - temp.start + 1;
temp = area[i];
}
}
count += temp.end - temp.start + 1;

printf("%d\n", L + 1 - count);

return 0;
}

整个算法的时间复杂度是 O(M * logM) + O(M)…