這是清華大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課程期末考試的第一道編程題，我在這篇文章中記錄了我從頭到尾解題的思維過(guò)程和對(duì)怎樣解題的思考劳较。

1. 題目描述

描述

數(shù)軸上有n個(gè)點(diǎn)，對(duì)于任一閉區(qū)間 [a, b]状勤，試計(jì)算落在其內(nèi)的點(diǎn)數(shù)吴侦。

輸入

第一行包括兩個(gè)整數(shù)：點(diǎn)的總數(shù)n，查詢的次數(shù)m杂靶。

第二行包含n個(gè)數(shù)梆惯，為各個(gè)點(diǎn)的坐標(biāo)。

以下m行伪煤，各包含兩個(gè)整數(shù)：查詢區(qū)間的左加袋、右邊界a和b。

輸出

對(duì)每次查詢抱既，輸出落在閉區(qū)間[a, b]內(nèi)點(diǎn)的個(gè)數(shù)职烧。

樣例

input

5 2
1 3 7 9 11
4 6
7 12

output

0
3

限制

• 0 ≤ n, m ≤ 5*10^5

• 對(duì)于每次查詢的區(qū)間[a, b]，都有a <= b

• 各點(diǎn)的坐標(biāo)互異

• 各點(diǎn)的坐標(biāo)防泵、查詢區(qū)間的邊界a蚀之、b，均為不超過(guò)10^7的非負(fù)整數(shù)

• 時(shí)間：2 sec

• 內(nèi)存：256 MB

2. 最簡(jiǎn)單粗暴的方法

要想解決問(wèn)題捷泞，首先要理解問(wèn)題足删。未知量是什么？已知數(shù)據(jù)是什么锁右？條件是什么失受？從這道題來(lái)看，未知量就是區(qū)間內(nèi)點(diǎn)的個(gè)數(shù)咏瑟；已知數(shù)據(jù)是數(shù)軸上的n個(gè)點(diǎn)和一個(gè)閉區(qū)間[a, b]拂到；條件如下：

1. n和m是不大于5*10^5次方的非負(fù)整數(shù)
2. 閉區(qū)間[a, b]保證a <= b，也就是閉區(qū)間左端點(diǎn)有可能等于右端點(diǎn)
3. 數(shù)軸上的n個(gè)點(diǎn)互不相等码泞，不會(huì)出現(xiàn)相等的元素兄旬，這里暗示數(shù)軸上的點(diǎn)構(gòu)成了一個(gè)點(diǎn)的集合（是不是可以利用一些集合的性質(zhì)？）
4. 點(diǎn)的坐標(biāo)余寥，區(qū)間的邊界a领铐、b都是小于10^7的非負(fù)整數(shù)，這里暗示點(diǎn)和區(qū)間邊界的取值都限定在一個(gè)固定范圍內(nèi)
5. 算法運(yùn)行的時(shí)間必須在2s內(nèi)
6. 算法占用的空間不得大于256MB

給定數(shù)軸上點(diǎn)的集合S和閉區(qū)間[a, b]宋舷，求S在[a, b]中點(diǎn)的個(gè)數(shù)绪撵。可以馬上想到的一種未知量和已知數(shù)據(jù)之間的聯(lián)系是：遍歷集合S上的每一個(gè)點(diǎn)s祝蝠，檢查s是不是滿足條件a <= s <= b音诈，如果是則計(jì)數(shù)汹来，最后得到的計(jì)數(shù)值count就是要求的結(jié)果。還可以做一點(diǎn)小的“優(yōu)化”：我將S中比a小的元素逐一排除改艇，然后再對(duì)比剩下的元素并計(jì)數(shù)收班，于是就有了如下的代碼：

// 算法1
#include <iostream>
using namespace std;

int range(int *pInt, int n, int a, int i);

int main() {
    int n, m;
    cin >> n >> m;

    int *points = new int[n];
    int *answer = new int[m];

    for (int i = 0; i < n; i++) {
        cin >> points[i];
    }

    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        answer[i] = range(points, n, a, b);
    }

    for (int i = 0; i < m; i++) {
        cout << answer[i] << endl;
    }

    delete[] points;
    delete[] answer;
    return 0;
}

// 核心算法
int range(int *pInt, int n, int a, int b) {
    // 先排除掉所有小于a的元素
    int *ptr = pInt;
    while (*ptr < a && ptr < pInt + n) {
        ptr++;
    }

    // 對(duì)剩下的元素進(jìn)行計(jì)數(shù)并返回結(jié)果
    int count = 0;
    for (; ptr < pInt + n; ptr++) {
        if (a <= *ptr && *ptr <= b) {
            count++;
        }
    }

    return count;
}

毫無(wú)疑問(wèn)地，如此brute-force的方法提交到OJ谒兄，只得了55分——OJ提供了20個(gè)測(cè)試用例摔桦，每個(gè)5分，除了前面11個(gè)通過(guò)了承疲，剩下的9個(gè)全部超時(shí)了邻耕。那么上面的這個(gè)算法有什么問(wèn)題呢？仔細(xì)觀察并思考后不難發(fā)現(xiàn)燕鸽，我們所做的這種“優(yōu)化”其實(shí)是徒勞的：算法仍然針對(duì)每個(gè)[a, b]遍歷了整個(gè)數(shù)軸上的點(diǎn)兄世，并一一做了比較。如果我們有m個(gè)閉區(qū)間啊研，點(diǎn)集S大小為n御滩，那么算法1的效率就是O(m * n)，這顯然是無(wú)法接受的党远。

而且削解，算法1還有一個(gè)隱含的問(wèn)題。仔細(xì)想想沟娱，題目條件中并沒(méi)有說(shuō)輸入的數(shù)軸上的點(diǎn)是有序的氛驮，而算法1卻隱含假定了points數(shù)組中的元素是按單調(diào)遞增的順序排列的，這顯然不對(duì)济似。況且矫废，這個(gè)解決方案并沒(méi)有將題目中所有的條件都用上∨榇溃看來(lái)我們還得繼續(xù)深入思考蓖扑。

3. 第一次嘗試改進(jìn)

雖然簡(jiǎn)單粗暴的算法并不滿足題目要求，但它也不是完全沒(méi)有意義娩脾，它是我們改進(jìn)算法的起點(diǎn)赵誓。此后產(chǎn)生的任何改進(jìn)版本打毛，其效率都會(huì)優(yōu)于它柿赊。通過(guò)分析算法1這個(gè)簡(jiǎn)單粗暴的版本，我們可以發(fā)現(xiàn)它的問(wèn)題就在于對(duì)數(shù)軸上的每個(gè)元素都做了一一比較幻枉，算法一次只能前進(jìn)一小步碰声，亦步亦趨。有很多比較是無(wú)效的熬甫。所以一種改進(jìn)算法的思路就是減少比較的次數(shù)胰挑。如果算法1做了100次比較，而經(jīng)過(guò)優(yōu)化后的算法只比較10次，那么效率就大大提高了瞻颂。

如果已知數(shù)據(jù)和未知量之間并沒(méi)有看上去那么直接的聯(lián)系豺谈，那么我們就要找與之相關(guān)的輔助題目，通過(guò)解決輔助題目來(lái)解決原題贡这。就好比中學(xué)的時(shí)候解幾何題茬末，我們是通過(guò)作輔助線將原題轉(zhuǎn)化為與之相關(guān)的一道輔助題目進(jìn)行求解一樣。

觀察未知量：數(shù)軸上的點(diǎn)在閉區(qū)間[a, b]范圍內(nèi)的點(diǎn)的個(gè)數(shù)盖矫。對(duì)于數(shù)軸上的點(diǎn)[1, 3, 7, 9, 11]丽惭，要求[7, 12]上點(diǎn)的個(gè)數(shù)，首先看大于等于區(qū)間左端點(diǎn)7的元素有哪些：[7, 9, 11]辈双，再看小于等于區(qū)間右端點(diǎn)12的元素有哪些：[1, 3, 7, 9, 11]责掏，它們的交集是：[7, 9, 11]，所以結(jié)果是3湃望。也就是說(shuō)：

1. 找到大于等于區(qū)間左端點(diǎn)7的最小元素7
2. 找到小于等于區(qū)間右端點(diǎn)12的最大元素11
3. 統(tǒng)計(jì)數(shù)軸上在7和11之間的元素個(gè)數(shù)换衬，得到3

我們其實(shí)是分別找了區(qū)間左端點(diǎn)a和區(qū)間右端點(diǎn)b在數(shù)軸上的位置，然后通過(guò)位置來(lái)確定元素個(gè)數(shù)的证芭。找某個(gè)元素在有序數(shù)組中的索引位置（又叫秩）冗疮，你能想到一種與它有關(guān)的算法嗎？有了檩帐！二分查找法不就擅長(zhǎng)處理這樣的問(wèn)題嗎术幔？嗯！看來(lái)這個(gè)點(diǎn)值得深挖湃密！那我們能利用它的方法诅挑，還是結(jié)果？對(duì)于這道題而言泛源，既利用了方法又利用了結(jié)果拔妥。我們知道，相比線性查找O(n)达箍，它的時(shí)間復(fù)雜度是O(logn)没龙，優(yōu)化效果明顯（這里開(kāi)始調(diào)動(dòng)基礎(chǔ)知識(shí)），因此方向應(yīng)該是正確的缎玫；而二分搜索法硬纤，恰恰適合用來(lái)快速定位元素在數(shù)組中的位置（哪怕它并不存在于數(shù)組中）。于是赃磨，我們寫(xiě)出如下算法：

// 算法2
#include <iostream>
#include <cstdlib>
using namespace std;

int range(int *pInt, int n, int a, int b);
int comp(const void *a, const void *b);
int *find_first_gte(int *pInt, int l, int r, int t);
int *find_first_lte(int *pInt, int l, int r, int t);

int main() {
    int n, m;
    cin >> n >> m;

    int *points = new int[n];
    int *answer = new int[m];

    for (int i = 0; i < n; i++) {
        cin >> points[i];
    }

    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        answer[i] = range(points, n, a, b);
    }

    for (int i = 0; i < m; i++) {
        cout << answer[i] << endl;
    }

    delete[] points;
    delete[] answer;
    return 0;
}

int range(int *pInt, int n, int a, int b) {
    // 先對(duì)數(shù)組做一個(gè)排序
    qsort(pInt, n, sizeof(int), comp);
    // 找有序數(shù)組中筝家，第一個(gè)大于等于a的元素
    int *p1 = find_first_gte(pInt, 0, n-1, a);
    // 找有序數(shù)組中，第一個(gè)小于等于b的元素
    int *p2 = find_first_lte(pInt, 0, n-1, b);

    // 通過(guò)手寫(xiě)結(jié)果并進(jìn)行大量觀察歸納總結(jié)可知邻辉，下面這個(gè)值就是我們想要的結(jié)果
    return (p2 - p1) + 1;
}

int *find_first_lte(int *pInt, int l, int r, int t) {
    int *pos = nullptr;

    // 借鑒了二分搜索的思路溪王，定位元素的位置腮鞍，并返回代表該位置的指針，下同
    while (l <= r) {
        int m = (l + r) / 2;
        if (t == pInt[m]) {
            pos = pInt + m;
            break;
        } else if (t < pInt[m]) {
            r = m - 1;
            pos = pInt + r;
        } else {
            l = m + 1;
            pos = pInt + m;
        }
    }
    return pos;
}

int *find_first_gte(int *pInt, int l, int r, int t) {
    int *pos = nullptr;

    while (l <= r) {
        int m = (l + r) / 2;
        if (t == pInt[m]) {
            pos = pInt + m;
            break;
        } else if (t < pInt[m]) {
            r = m - 1;
            pos = pInt + m;
        } else {
            l = m + 1;
            pos = pInt + l;
        }
    }
    return pos;
}

int comp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

把算法2提交到OJ莹菱，滿懷期待地等待結(jié)果移国。一看，大失所望道伟！還是55分桥狡，怎么回事，怎么優(yōu)化后的算法居然和算法1得到的是一樣的分?jǐn)?shù)皱卓？裹芝！仔細(xì)檢查了一下代碼，發(fā)現(xiàn)一個(gè)問(wèn)題娜汁，我把qsort寫(xiě)到range函數(shù)中了嫂易，也就是說(shuō)每次執(zhí)行我都要毫無(wú)意義地把points數(shù)組重新排序一遍，這是沒(méi)有必要的掐禁！將它移動(dòng)到main函數(shù)中怜械，只排序一次：

int main() {
    int n, m;
    cin >> n >> m;

    int *points = new int[n];
    int *answer = new int[m];

    for (int i = 0; i < n; i++) {
        cin >> points[i];
    }

    qsort(points, n, sizeof(int), comp);

    int a, b;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        answer[i] = range(points, n, a, b);
    }

    for (int i = 0; i < m; i++) {
        cout << answer[i] << endl;
    }

    delete[] points;
    delete[] answer;
    return 0;
}

再次提交OJ系統(tǒng)，分?jǐn)?shù)提高到了90傅事，有進(jìn)步缕允！但還有2個(gè)測(cè)試用例超時(shí)了。要拿到100分蹭越，真心不容易障本！

4. 無(wú)頭蒼蠅閃亮登場(chǎng)

我開(kāi)始有點(diǎn)心急了。仔細(xì)檢查了一下算法响鹃，我已經(jīng)用了快速排序算法qsort驾霜，以及二分查找法，前者的復(fù)雜度是O(nlogn)买置，后者的效率是O(logn)粪糙。對(duì)于m個(gè)閉區(qū)間而言，總的就是O(nlogn+mlogn) = O(nlogn)忿项，效率已經(jīng)不差了蓉冈。難道還不滿足題目要求？

那我們還有什么可優(yōu)化的空間嗎轩触？算法2的解決方案為了找元素的秩寞酿，將整個(gè)數(shù)軸上的點(diǎn)進(jìn)行了排序，能不能不排序找到元素的秩怕膛？這使我想到了快速排序算法中的partition方法熟嫩，它的效率大約在1.35logn左右秦踪。試過(guò)之后發(fā)現(xiàn)分?jǐn)?shù)仍然是90分褐捻，沒(méi)有效果掸茅。

終于還是忍不住上網(wǎng)搜了一下別人的答案，發(fā)現(xiàn)有人提出可以根據(jù)“各點(diǎn)的坐標(biāo)柠逞、查詢區(qū)間的邊界a昧狮、b，均為不超過(guò)10^7的非負(fù)整數(shù)”這一條件板壮，使用計(jì)數(shù)排序來(lái)對(duì)數(shù)組進(jìn)行排序逗鸣。這個(gè)算法針對(duì)有特定取值范圍的數(shù)進(jìn)行排序能達(dá)到O(n)的復(fù)雜度，要優(yōu)于快速排序的O(nlogn)绰精，于是我自己寫(xiě)了個(gè)計(jì)數(shù)排序算法撒璧，好家伙，不但效率沒(méi)提高笨使，還喜提了一個(gè)錯(cuò)誤結(jié)果卿樱，變成了85分。

在此之后硫椰，我進(jìn)行了各種猜測(cè)繁调，各種嘗試，得到的分?jǐn)?shù)也琳瑯滿目：80分靶草、15分蹄胰、0分……90分就像一個(gè)無(wú)法逾越的障礙，擋在我前進(jìn)的道路上奕翔。我開(kāi)始有點(diǎn)煩躁了裕寨，像個(gè)無(wú)頭蒼蠅一樣這試試那試試。連猜帶蒙派继，都無(wú)一例外全部失敗了帮坚。晚上加班回家9點(diǎn)過(guò)，洗完澡開(kāi)始解題到12點(diǎn)過(guò)互艾，早上六點(diǎn)過(guò)起床试和，再解題，然后再匆匆忙忙跑去上班纫普，甚至一邊開(kāi)車還在一邊琢磨自己到底錯(cuò)在哪阅悍？

5. 重新冷靜下來(lái)

一直這樣下去并不是辦法，我必須先冷靜下來(lái)昨稼，然后再仔細(xì)思考节视。首先，大方向上思路有沒(méi)有問(wèn)題假栓？沒(méi)有問(wèn)題寻行！網(wǎng)上別人的答案也是“排序+二分查找”的整體思路。我將這個(gè)問(wèn)題拆解為排序和（二分）查找的解決方案是正確的匾荆。

那么只可能是“排序”或者“二分查找”的算法有問(wèn)題了拌蜘！這個(gè)可能性很大杆烁，因?yàn)橛?jì)數(shù)排序和二分查找都是我寫(xiě)的，并沒(méi)有經(jīng)過(guò)充分的測(cè)試简卧！Wrong Answer就是我在替換了自己寫(xiě)的計(jì)數(shù)排序算法后出現(xiàn)的兔魂，肯定寫(xiě)的有問(wèn)題！

另外举娩，在網(wǎng)上參考別人的實(shí)現(xiàn)思路的過(guò)程中析校，我發(fā)現(xiàn)有人也用qsort圓滿解決了問(wèn)題，還有人自己手寫(xiě)歸并排序的铜涉，說(shuō)明使用qsort并不是導(dǎo)致超時(shí)的原因智玻。而且某個(gè)人在他的博客中提到，要用C語(yǔ)言的scanf和printf進(jìn)行輸入輸出芙代，不要用C++的cin和cout尚困，前者效率更高。難道是這個(gè)原因?qū)е鲁瑫r(shí)链蕊？我試驗(yàn)了一下事甜，果然，分?jǐn)?shù)提高到了95分滔韵，只有一個(gè)Wrong Answer逻谦，所有的用例都在規(guī)定時(shí)間內(nèi)計(jì)算完成了！居然是因?yàn)檫@個(gè)原因陪蜻，真是無(wú)語(yǔ)邦马！

于是我把代碼重新調(diào)整了一下，仍然使用C標(biāo)準(zhǔn)庫(kù)中的qsort對(duì)元素進(jìn)行排序宴卖。但我對(duì)之前寫(xiě)的基于指針的二分查找不太滿意滋将，想改成基于數(shù)組索引的。于是我把《數(shù)據(jù)結(jié)構(gòu)》這本書(shū)有關(guān)二分查找的章節(jié)仔細(xì)閱讀了一下症昏，并認(rèn)真思考：我要怎樣利用二分查找法來(lái)定位元素在數(shù)組中的位置随闽？如果該元素并不存在于數(shù)組中，算法該返回什么肝谭？在我看來(lái)掘宪，如果元素存在于數(shù)組中，那么算法自然要返回元素在數(shù)組中的秩攘烛；如果元素不在數(shù)組中魏滚，那么算法應(yīng)該返回元素插入到數(shù)組后的秩，也就是原數(shù)組中大于等于該元素的最小元素的秩坟漱。例如對(duì)于[1, 3, 7, 9, 11]鼠次，對(duì)元素6進(jìn)行二分查找應(yīng)該返回結(jié)果2，因?yàn)?將被插入到數(shù)組中秩為2的位置，得到[1, 3, 6, 7, 9, 11]

假設(shè)閉區(qū)間[a, b]端點(diǎn)都在數(shù)組中腥寇，那么對(duì)于[1, 3, 7, 9, 11]成翩，如果要求[3, 9]中元素的個(gè)數(shù)，因?yàn)?的秩是1花颗，9的秩是3捕传，3-1+1 = 3惠拭，元素個(gè)數(shù)就是3扩劝。

如果閉區(qū)間[a, b]端點(diǎn)不都在數(shù)組中，那么就有3種情況：（1）a在b不在职辅；（2）a不在b在棒呛；（3）a和b都不在。這3種情況下閉區(qū)間中元素個(gè)數(shù)又是多少呢域携？為此我構(gòu)造了一些用例簇秒，進(jìn)行計(jì)算并找規(guī)律：

對(duì)于數(shù)組[1, 3, 7, 9, 11]，對(duì)于閉區(qū)間集合{[4, 6], [7, 12], [6, 6], [7, 7], [3, 11], [0, 0], [13, 13], [6, 12], [1, 13], [6, 11], [4, 11], [1, 4], [0, 7], [3, 7], [0, 13], [2, 8]}秀鞭，有：

1. [4, 6]：indexA = 2趋观，indexB = 2，count = 0（a和b都不在）
2. [7, 12] ：indexA = 2锋边，indexB = 5皱坛，count = 3（a在b不在）
3. [6, 6] ：indexA = 2，indexB = 2豆巨，count = 0（a和b都不在）
4. [7, 7]：indexA = 2剩辟，indexB = 2，count = 1（a和b都在）
5. [3, 11]：indexA = 1往扔，indexB = 4贩猎，count = 4（a和b都在）
6. [0, 0] ：indexA = 0，indexB = 0萍膛，count = 0（a和b都不在）
7. [13, 13] ：indexA = 5吭服，indexB = 5，count = 0（a和b都不在）
8. [6, 12]：indexA = 2蝗罗，indexB = 5噪馏，count = 3（a和b都不在）
9. [1, 13]：indexA = 0，indexB = 5绿饵，count = 5（a在b不在）
10. [6, 11]：indexA = 2欠肾，indexB = 4，count = 3（a不在b在）
11. [4, 11]：indexA = 2拟赊，indexB = 4刺桃，count = 3（a不在b在）
12. [1, 4]：indexA = 0，indexB = 2吸祟，count = 2（a在b不在）
13. [0, 7]：indexA = 0瑟慈，indexB = 2桃移，count = 3（a不在b在）
14. [3, 7]：indexA = 1，indexB = 2葛碧，count = 2（a和b都在）
15. [0, 13] ：indexA = 0借杰，indexB = 5，count = 5（a和b都不在）
16. [2, 8]：indexA = 1进泼，indexB = 3蔗衡，count = 2（a和b都不在）

看出規(guī)律來(lái)了：

1. a和b都不在：indexB - indexA
2. a和b都在：indexB - indexA + 1
3. a在b不在：indexB - indexA
4. a不在b在：indexB - indexA + 1

再進(jìn)一步歸納一下：

1. 閉區(qū)間[a, b]，若b存在于數(shù)組中乳绕，則count = indexB - indexA + 1
2. 閉區(qū)間[a, b]绞惦，若b不存在于數(shù)組中，則count = indexB - indexA

外加把cin/cout換成scanf/printf洋措，以及重新采用qsort济蝉，得到如下算法：

// 算法3
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int range(int *pInt, int n, int a, int b);
int find_index_of(const int *pInt, int lo, int hi, int t);
int comp(const void *a, const void *b);

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    int *points = new int[n];
    int *answer = new int[m];

    for (int i = 0; i < n; i++) {
        scanf("%d", points+i);
    }

    qsort(points, n, sizeof(int), comp);

    int a, b;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        answer[i] = range(points, n, a, b);
    }

    for (int i = 0; i < m; i++) {
        printf("%d\n", answer[i]);
    }

    delete[] points;
    delete[] answer;
    return 0;
}

int comp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int range(int *pInt, int n, int a, int b) {

    int indexA = find_index_of(pInt, 0, n, a);
    int indexB = find_index_of(pInt, 0, n, b);

    int count = 0;
    if (indexB < n && pInt[indexB] == b) {
        count = indexB - indexA + 1;
    } else if (indexB >= n || (indexB < n && pInt[indexB] != b)) {
        count = indexB - indexA;
    }
    return count;
}

int find_index_of(const int *pInt, int lo, int hi, int t) {
    while (lo < hi) {
        int mi = (lo + hi) / 2;
        if (t < pInt[mi])
            hi = mi;
        else if (pInt[mi] < t)
            lo = mi + 1;
        else
            return mi;
    }
    return lo;
}

find_index_of是二分查找法基礎(chǔ)上做了一點(diǎn)小小的修改。標(biāo)準(zhǔn)的二分查找法菠发，當(dāng)元素沒(méi)有找到時(shí)返回-1王滤，表示數(shù)組中不存在這個(gè)元素，這里返回的是元素待插入的位置的秩滓鸠，也就是數(shù)組中大于等于元素的最小的那個(gè)元素雁乡。二分查找法看似簡(jiǎn)單，實(shí)際在編寫(xiě)的時(shí)候要特別注意邊界值哥力。一般來(lái)說(shuō)蔗怠，按照在S[lo, hi)這個(gè)左閉右開(kāi)區(qū)間進(jìn)行查找的方式編寫(xiě)党饮，能夠得到形式統(tǒng)一且簡(jiǎn)潔的實(shí)現(xiàn)咒彤，所以對(duì)于右邊界而言是hi = mi，而對(duì)于左邊界而言豫柬，則是lo = mi + 1锌钮，這些細(xì)節(jié)值得注意桥温，我一開(kāi)始的幾個(gè)實(shí)現(xiàn)中就是吃了這些細(xì)節(jié)的虧，導(dǎo)致得到的結(jié)果并不總是正確梁丘。

上傳解決方案到OJ侵浸，得到100分，完全通過(guò)氛谜！

6. 那么掏觉，該怎樣解題呢？

從根本上說(shuō)值漫，要重視基礎(chǔ)澳腹，要認(rèn)真理解基本概念，復(fù)雜問(wèn)題無(wú)非就是簡(jiǎn)單問(wèn)題的約束性組合。有扎實(shí)的基礎(chǔ)酱塔，再加上思維方式的訓(xùn)練沥邻，你就能透過(guò)復(fù)雜問(wèn)題看到它背后都是由哪些基本問(wèn)題通過(guò)什么方式組合在一起的。這些基本問(wèn)題又能還原為哪些基本操作羊娃。

有了基礎(chǔ)還不夠唐全，還要訓(xùn)練思維方式。匈牙利數(shù)學(xué)家喬治·波利亞在他的書(shū)《怎樣解題：數(shù)學(xué)思維的新方法》中蕊玷，介紹了解題的”內(nèi)功心法“：

• 第一邮利，你必須理解題目：
  • 未知量是什么？
  • 已知數(shù)據(jù)是什么集畅？
  • 條件是什么近弟？
  • 條件有可能滿足嗎缅糟？條件是否足以確定未知量挺智？或者它不夠充分？或者多余窗宦？或者矛盾赦颇？
  • 畫(huà)一張圖，引入適當(dāng)?shù)姆?hào)赴涵。
  • 將條件的不同部分分開(kāi)媒怯。你能把它們寫(xiě)出來(lái)嗎？
• 第二髓窜，找出已知數(shù)據(jù)與未知量之間的聯(lián)系扇苞。如果找不到直接的聯(lián)系，你也許不得不去考慮輔助題目寄纵。最終你應(yīng)該得到一個(gè)解題方案鳖敷。
  • 你以前見(jiàn)過(guò)它嗎？或者你見(jiàn)過(guò)同樣的題目以一種稍有不同的形式出現(xiàn)嗎程拭？
  • 你知道一道與它有關(guān)的題目嗎定踱？你知道一條可能有用的定理嗎？
  • 觀察未知量恃鞋！并盡量想出一道你所熟悉的具有相同或相似未知量的題目崖媚。
  • 這里有一道題目和你的題目有關(guān)而且以前解過(guò)。你能利用它嗎恤浪？你能利用它的結(jié)果嗎畅哑？你能利用它的方法嗎？為了有可能應(yīng)用它水由，你是否應(yīng)該引入某個(gè)輔助元素荠呐？
  • 你能重新敘述這道題目嗎？你還能以不同的方式敘述它嗎？
  • 回到定義上去直秆。
  • 如果你不能解所提的題目濒募，先嘗試去解某道有關(guān)的題目。你能否想到一道更容易著手的相關(guān)題目圾结？一道更為普遍化的題目瑰剃？一道更為特殊化的題目？一道類似的題目筝野？你能解出這道題目的一部分嗎晌姚？只保留條件的一部分，而丟掉其他部分歇竟，那么未知量可以確定到什么程度挥唠，它怎樣變化？你能從已知數(shù)據(jù)中得出一些有用的東西嗎焕议？你能想到其他合適的已知數(shù)據(jù)來(lái)確定該未知量嗎宝磨？你能改變未知量或已知數(shù)據(jù)，或者有必要的話盅安，把兩者都改變唤锉，從而使新的未知量和新的已知數(shù)據(jù)彼此更接近嗎？你用到所有的已知數(shù)據(jù)了嗎别瞭？你用到全部的條件了嗎窿祥？你把題目中所有的關(guān)鍵概念都考慮到了嗎？
• 第三蝙寨，執(zhí)行你的方案晒衩。
  • 執(zhí)行你的解題方案，檢查每一個(gè)步驟墙歪。
  • 你能清楚地看出這個(gè)步驟是正確的嗎听系？
  • 你能否證明它是正確的？
• 第四箱亿，檢查已經(jīng)得到的解答跛锌。
  • 你能檢驗(yàn)這個(gè)結(jié)果嗎？
  • 你能檢驗(yàn)這個(gè)論證嗎届惋？
  • 你能以不同的方式推導(dǎo)這個(gè)結(jié)果嗎髓帽？
  • 你能一眼就看出它來(lái)嗎？
  • 你能在別的什么題目中利用這個(gè)結(jié)果或這種方法嗎脑豹？

如果能在解題的過(guò)程中有意識(shí)地使用這些問(wèn)題和建議郑藏，也許就能幫助找到解決問(wèn)題的思路，也就是聯(lián)系已知數(shù)據(jù)和未知量的那個(gè)”橋梁“瘩欺。更多的例子必盖，請(qǐng)閱讀這本書(shū)拌牲，它不光適用于解決數(shù)學(xué)題，還適用于解決編程題乃至其他的一些問(wèn)題歌粥。

7. 辯證唯物主義的”知行合一“觀

書(shū)本上的知識(shí)塌忽，讀了不用，很快就會(huì)忘掉失驶，光看書(shū)解決不了問(wèn)題土居，還容易讀成教條主義書(shū)呆子。不讀書(shū)嬉探，野路子出身擦耀，僅憑經(jīng)驗(yàn)去解決問(wèn)題，容易變成經(jīng)驗(yàn)主義的坎井之蛙涩堤。怎么看待理論和實(shí)踐的關(guān)系眷蜓？這個(gè)問(wèn)題困擾了我很久，現(xiàn)在我找到答案了胎围。那就是要統(tǒng)一在辯證唯物主義的知行合一觀下吁系。就是“實(shí)事求是”。

“‘實(shí)事’就是客觀存在著的一切事物痊远，‘是’就是客觀事物的內(nèi)部聯(lián)系垮抗，即規(guī)律性氏捞，‘求’就是我們?nèi)パ芯勘檀稀！?/p>

——毛澤東

我們?cè)谟龅揭粋€(gè)問(wèn)題的時(shí)候液茎，要憑借良好的基礎(chǔ)逞姿、認(rèn)真的觀察、仔細(xì)的思考以及調(diào)查研究將其“解壓縮”成一些基本問(wèn)題的有機(jī)組合捆等，這個(gè)過(guò)程不斷深入下去滞造，不斷拆解，直到問(wèn)題變成幾個(gè)基本知識(shí)的組合栋烤。即研究出事物內(nèi)部的規(guī)律性的東西谒养。如果中間有哪個(gè)地方卡殼了，那就說(shuō)明自己的知識(shí)框架在這一部分存在漏洞明郭，這個(gè)漏洞導(dǎo)致自己無(wú)法對(duì)事物產(chǎn)生正確的認(rèn)識(shí)买窟，那就要通過(guò)學(xué)習(xí)理論知識(shí)去補(bǔ)上這個(gè)漏洞，從而重新建立對(duì)客觀事物的正確認(rèn)識(shí)薯定，然后再用正確的認(rèn)識(shí)去指導(dǎo)實(shí)踐始绍。

如果連問(wèn)題都看不懂，或者完全沒(méi)思路话侄，說(shuō)明漏洞還有點(diǎn)大亏推，這個(gè)時(shí)候就應(yīng)該把問(wèn)題先放一放学赛，先帶著問(wèn)題去學(xué)一學(xué)理論知識(shí)，這個(gè)時(shí)候的主要矛盾是缺乏解決問(wèn)題的基礎(chǔ)知識(shí)吞杭。等基礎(chǔ)知識(shí)掌握到一定程度了盏浇，就可以邊實(shí)踐邊研究理論知識(shí)。等對(duì)解決一般問(wèn)題駕輕就熟了芽狗，就可以不那么依靠書(shū)本而解決更多更復(fù)雜的問(wèn)題了缠捌。這就好比逐步扔掉拐杖自己學(xué)會(huì)走路一樣，通過(guò)實(shí)踐的訓(xùn)練是可以做到的译蒂。