map 模板類

#include <map> 
#include <string>
#include <cstdlib>
#include <iostream>

using namespace std;

int main(){

定義一個(gè) map，Key 為字符串，Value 為整數(shù)。（想用CString，似乎只有 MFC 才有這個(gè)）

    typedef map<string, int> str_int_map;
    str_int_map myMap;

插入鍵值對(duì)有三種方法。

• 用 insert 時(shí)，插入 Key 的已有，則插入失敗，可以用其返回的 pair<str_int_map::iterator, bool> 來查看插入是否成功。pair 的第一個(gè)變量是一個(gè) map 的迭代器，第二個(gè)變量是 bool，如果插入成功 .second 為真。

• 用方括號(hào)（有點(diǎn)像 py）時(shí)，如果 Key 已有則新的值會(huì)覆蓋舊的值。

    pair<str_int_map::iterator, bool> insert_pair;

    insert_pair = myMap.insert(pair<string, int>("drei", 3)); cout << insert_pair.second << endl;
    insert_pair = myMap.insert(pair<string, int>("vier", 4)); cout << insert_pair.second << endl;

    insert_pair = myMap.insert(str_int_map::value_type("eins", 1)); cout << insert_pair.second << endl;
    insert_pair = myMap.insert(str_int_map::value_type("zwei", 2)); cout << insert_pair.second << endl;

    myMap["funf"] = 5;
    myMap["sechs"] = 6;

看大小用 size()。

    cout << "myMap.size = " << myMap.size() << endl;

遍歷用迭代器, begin(), end(), rbegin(), rend(), ++。

    str_int_map::iterator iter;
    for(iter = myMap.begin(); iter != myMap.end(); iter ++){
        cout << iter->first << " " << iter->second << '\n';
    }

    str_int_map::reverse_iterator riter;
    for(riter = myMap.rbegin(); riter != myMap.rend(); riter ++){
        cout << riter->first << " " << riter->second << '\n';
    }

根據(jù) Key 查找 Value 用 find()。用 Key 填進(jìn)中括號(hào)好像也行。如果查不到，返回 end() 的值。

    cout << myMap["zwei"] << endl;
    str_int_map::iterator iterf = myMap.find("funf");
    if(iterf != myMap.end()) cout << "Find funf = " << iterf->second << endl; else cout << "Not found\n";

刪除用 erase()， 參數(shù)可以傳：

• iterator erase（iterator it);//通過一個(gè)條目對(duì)象刪除
• iterator erase（iterator first，iterator last）//刪除一個(gè)范圍
• size_type erase(const Key&key);//通過關(guān)鍵字刪除

clear()就相當(dāng)于enumMap.erase(enumMap.begin(),enumMap.end());

刪掉它：

    myMap.erase(iterf);

然后就找不到啦，會(huì)返回 end()：

    iterf = myMap.find("funf");
    if(iterf != myMap.end()) cout << "Find funf = " << iterf->second << endl; else cout << "Not found\n";

over:

    system("pause");
    return 0;
}

map 是一棵紅！黑！樹！就是最不會(huì)寫的那種樹！就是上次考試時(shí)用了能多賺一個(gè) case 的那棵樹！是不是很想把各種奇葩數(shù)據(jù)都搞成結(jié)構(gòu)體然后存進(jìn)去，就可以為所欲為了~

map 中的元素是自動(dòng)按 Key 升序排序，默認(rèn)是采用小于號(hào)來排序的，所以自己的類型得重載一下 < ……啊重載函數(shù)怎么寫的來著……之后遇到題的話再寫一下吧……

1071 SpeechPatterns 字符串 map/hash

找出現(xiàn)次數(shù)最多的單詞。

因?yàn)閷?shí)在沒有思路，感覺自己寫一定超時(shí)，只好學(xué)了一下 map。

后來還是超時(shí)了，是因?yàn)槲覄傞_始把字符全都讀進(jìn)了大數(shù)組，然后一個(gè)一個(gè)挑。后來想起來可以直接 getchar()。剛開始我還把臨時(shí)組成的單詞存在 char[] 里，然后再轉(zhuǎn)換成 string，也是夠嗆的。后來這些都改掉，就過啦。

寫出來的 c和 c++的混血兒也是夠嗆的：

# include <string>
# include <map>
# include <cstdio>
# include <cstring>
# include <iostream>

using namespace std;

typedef map<string, int> str_int_map;

char c;
string w;

int main() {
    str_int_map myMap;

    while((c = getchar()) != '\n') {
        if ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) {
            w += c; //string 可以 += ，相當(dāng)于 strcat
        }
        else if (c >= 'A' && c <= 'Z') { //小寫
            w += (c - 'A' + 'a');
        }
        else if(! w.empty()){ // string 有這個(gè)
            if (myMap.find(w) == myMap.end()) { //查找
                myMap[w] = 1;
            }
            else {
                myMap[w] ++; //賦值查值都可以直接用方括號(hào)噠！
            } 
            w.clear(); // string 有這個(gè)
        }
    }
    if (!w.empty()) { //最后一個(gè)詞別忘了！
        if (myMap.find(w) == myMap.end()) {
            myMap[w] = 1;
        }
        else {
            myMap[w] ++;
        }
    }

    str_int_map::iterator iter; //迭代器
    string maxWord;
    int maxTime = 0;
    for (iter = myMap.begin(); iter != myMap.end(); iter++) {
        if (iter->second > maxTime) { // first, second
            maxTime = iter->second;
            maxWord = iter->first;
        }
    }
    
    cout << maxWord << " " << maxTime;

    return 0;
}

1070 Mooncake 簡(jiǎn)單 排序 ，沒過

有一個(gè)測(cè)試點(diǎn)通不過，答案錯(cuò)誤。?？途W(wǎng)上都通過了。

1069 The Black Hole 簡(jiǎn)單

略。秒過。

1068 Find More Coins 背包，最小解

給一堆硬幣，還有要求的總值，求能否組成這個(gè)值，能的話求出最小的硬幣序列。最小是按照字典順序從第一個(gè)數(shù)開始比的，比如 1+3+5 = 9 比 2+3+4 = 9 小。

不會(huì)做，差點(diǎn)暴搜。想著能不能把每種總量的硬幣選擇存成一個(gè)數(shù)組，但是似乎占內(nèi)存有點(diǎn)大，而且很蠢。

于是參考了 http://blog.csdn.net/xyt8023y/article/details/47255241，向這位同學(xué)表示感謝:-)

下圖是一個(gè)簡(jiǎn)單的 case，要用 9 塊錢，給了 1 2 3 4 5 7 這幾個(gè)硬幣。原始的 dp 表（同樣可以壓縮到一維數(shù)組用）如下，表中存的值 dp[i][j] 是“僅僅使用前 i 個(gè)硬幣時(shí)，能組成的不大于 j 的最大值?！币虼诉f推公式為dp[i][j] = max(dp[i - 1][j - c[i]] + c[i], dp[i - 1][j]，即要么用 c[i] 硬幣，要么不用。

到這里還和之前寫的 dp 沒多大區(qū)別，最多就是我存的值意思不一樣。又用了一個(gè)布爾數(shù)組 use[n_coin][max_value]來記錄“組成值 j 的時(shí)候，最優(yōu)解是否用了第 i 個(gè)硬幣”，值為真則在下圖中表示為淺灰色底色。

怎么找最小序列呢？硬幣的面值從大到小排列，在之后遇到 dp[i][j] 更新的時(shí)候就把 use[i][j]為真。如果用不用第 i 個(gè)硬幣，構(gòu)成的值都一樣，也是要更新的。這樣就把所用的硬幣的最小值往下拉，選用的總是更小的序列。比如本來用的 5，后面拿到了 2 和 3，就給更新掉。

image.png

當(dāng)表格填滿，就可以通過 dp[m] == m來判斷是否能構(gòu)成 m 塊錢了。至于硬幣序列，就用剛剛記錄的布爾數(shù)組往上挖，如藍(lán)色箭頭，構(gòu)成 9 用了 1，減掉 1，剩下的構(gòu)成 8 ，是用了 3，再減掉剩5， 構(gòu)成 5 就只是用了 5， 沒了。

代碼倒是很簡(jiǎn)短：

# include <cstdio>
# include <cstdlib>

int N, M; //n_coins; money_to_pay
bool use[10010][110]; //形成值j的時(shí)候，是否要用硬幣i
int dp[110]; //前面硬幣所能構(gòu)成的不大于i的最大值
int c[10010]; //硬幣面值,0-N

int compar(const void *a, const void *b) {
    return *(int*)b - *(int*)a; //降序
}

int main() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        scanf("%d", c + i);
    }

    qsort(c, N, sizeof(int), compar); //硬幣倒序

    for (int i = 0; i < N; i++) {
        for (int j = M; j >= c[i]; j--) {
            if (dp[j - c[i]] + c[i] >= dp[j]) { //有相等的情況也覆蓋
                dp[j] = dp[j - c[i]] + c[i];
                use[i][j] = true;
            }
        }
    }

    if (dp[M] != M) {
        printf("No Solution");
    }
    else {
        bool ans[10010] = { false };
        int i = N - 1, j = M;
        while (j != 0) {
            while (!use[i][j]) i--;
            ans[i] = true;
            j -= c[i];
            i--;
        }

        bool first = true;
        for (i = N - 1; i >= 0; i--) { //c[i]是從大到小的，得倒著數(shù)
            if (ans[i]) {
                if (!first) {
                    printf(" ");
                }
                else {
                    first = false;
                }
                printf("%d", c[i]);
            }
        }
    }
    
    return 0;
}