map 模板类

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

using namespace std;

int main(){

定义一个 map，Key 为字符串，Value 为整数。（想用CString，似乎只有 MFC 才有这个）

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

插入键值对有三种方法。

• 用 insert 时，插入 Key 的已有，则插入失败，可以用其返回的 pair<str_int_map::iterator, bool> 来查看插入是否成功。pair 的第一个变量是一个 map 的迭代器，第二个变量是 bool，如果插入成功 .second 为真。

• 用方括号（有点像 py）时，如果 Key 已有则新的值会覆盖旧的值。

    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';
    }

根据 Key 查找 Value 用 find()。用 Key 填进中括号好像也行。如果查不到，返回 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()， 参数可以传：

• iterator erase（iterator it);//通过一个条目对象删除
• iterator erase（iterator first，iterator last）//删除一个范围
• size_type erase(const Key&key);//通过关键字删除

clear()就相当于enumMap.erase(enumMap.begin(),enumMap.end());

删掉它：

    myMap.erase(iterf);

然后就找不到啦，会返回 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 是一棵红！黑！树！就是最不会写的那种树！就是上次考试时用了能多赚一个 case 的那棵树！是不是很想把各种奇葩数据都搞成结构体然后存进去，就可以为所欲为了~

map 中的元素是自动按 Key 升序排序，默认是采用小于号来排序的，所以自己的类型得重载一下 < ……啊重载函数怎么写的来着……之后遇到题的话再写一下吧……

1071 SpeechPatterns 字符串 map/hash

找出现次数最多的单词。

因为实在没有思路，感觉自己写一定超时，只好学了一下 map。

后来还是超时了，是因为我刚开始把字符全都读进了大数组，然后一个一个挑。后来想起来可以直接 getchar()。刚开始我还把临时组成的单词存在 char[] 里，然后再转换成 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 可以 += ，相当于 strcat
        }
        else if (c >= 'A' && c <= 'Z') { //小写
            w += (c - 'A' + 'a');
        }
        else if(! w.empty()){ // string 有这个
            if (myMap.find(w) == myMap.end()) { //查找
                myMap[w] = 1;
            }
            else {
                myMap[w] ++; //赋值查值都可以直接用方括号哒！
            } 
            w.clear(); // string 有这个
        }
    }
    if (!w.empty()) { //最后一个词别忘了！
        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 简单 排序 ，没过

有一个测试点通不过，答案错误。牛客网上都通过了。

1069 The Black Hole 简单

略。秒过。

1068 Find More Coins 背包，最小解

给一堆硬币，还有要求的总值，求能否组成这个值，能的话求出最小的硬币序列。最小是按照字典顺序从第一个数开始比的，比如 1+3+5 = 9 比 2+3+4 = 9 小。

不会做，差点暴搜。想着能不能把每种总量的硬币选择存成一个数组，但是似乎占内存有点大，而且很蠢。

于是参考了 http://blog.csdn.net/xyt8023y/article/details/47255241，向这位同学表示感谢:-)

下图是一个简单的 case，要用 9 块钱，给了 1 2 3 4 5 7 这几个硬币。原始的 dp 表（同样可以压缩到一维数组用）如下，表中存的值 dp[i][j] 是“仅仅使用前 i 个硬币时，能组成的不大于 j 的最大值。”因此递推公式为dp[i][j] = max(dp[i - 1][j - c[i]] + c[i], dp[i - 1][j]，即要么用 c[i] 硬币，要么不用。

到这里还和之前写的 dp 没多大区别，最多就是我存的值意思不一样。又用了一个布尔数组 use[n_coin][max_value]来记录“组成值 j 的时候，最优解是否用了第 i 个硬币”，值为真则在下图中表示为浅灰色底色。

怎么找最小序列呢？硬币的面值从大到小排列，在之后遇到 dp[i][j] 更新的时候就把 use[i][j]为真。如果用不用第 i 个硬币，构成的值都一样，也是要更新的。这样就把所用的硬币的最小值往下拉，选用的总是更小的序列。比如本来用的 5，后面拿到了 2 和 3，就给更新掉。

image.png

当表格填满，就可以通过 dp[m] == m来判断是否能构成 m 块钱了。至于硬币序列，就用刚刚记录的布尔数组往上挖，如蓝色箭头，构成 9 用了 1，减掉 1，剩下的构成 8 ，是用了 3，再减掉剩5， 构成 5 就只是用了 5， 没了。

代码倒是很简短：

# include <cstdio>
# include <cstdlib>

int N, M; //n_coins; money_to_pay
bool use[10010][110]; //形成值j的时候，是否要用硬币i
int dp[110]; //前面硬币所能构成的不大于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]是从大到小的，得倒着数
            if (ans[i]) {
                if (!first) {
                    printf(" ");
                }
                else {
                    first = false;
                }
                printf("%d", c[i]);
            }
        }
    }
    
    return 0;
}