STL 链表： List

初始化

1 2	#include<list> list<int> linklist;

在头部或尾部添加一个元素：

1
2
3

int head = 0;
linklist.push_front(head);
linklist.push_back(head);

遍历链表，并在值为x的节点后面，插入值为y的节点：

for(auto it=linklist.begin(); it!=linklist.end(); it++){
    if(*it==x){
        linklist.insert(++it, y);  //在指定位置插入
        break;
    }
}

删除节点：

//根据迭代器删除
iterator erase( iterator pos );
iterator erase( iterator start, iterator end );
//根据值删除
void remove( const TYPE &val );

结构体排序

题目大意：对录入的学生的分数进行升序或降序排列。原题链接

输入的第一行表示学生的人数n；第二行表示按升序(1)还是降序(0)来排列；接下来的n行是学生的名字和分数。如果有学生分数相同，则按照录入的顺序来输出。

输入：
3
0
fang 90
yang 50
ning 70
输出：
fang 90
ning 70
yang 50

关键是cmp函数要掌握！

话不多说，直接看代码：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

struct Node{
    string name;
    int score;
    int id;  //记录录入的先后顺序
};
Node node[201];

/*cmp1：分数大的排在前*/
bool cmp1(Node x, Node y){
    //如果分数相等，按照id小的排在前
    if(x.score == y.score) return x.id < y.id;
    return x.score > y.score;
}
/*cmp2：分数小的排在前*/
bool cmp2(Node x, Node y){
    //如果分数相等，按照id小的排在前
    if(x.score == y.score) return x.id < y.id;
    return x.score < y.score;
}
int main(){
    int n;
    //多组输入数据
    while(cin>>n){
        //order指明以升序或降序来排序
        int order;
        cin>>order;
        //读入n个学生的名字和分数
        for(int i=0;i<n;i++){
            cin>>node[i].name>>node[i].score;
            //id用来记录每条数据的录入顺序
            node[i].id = i;
        }
        //调用cmp函数
        if(order == 0) 
            sort(node, node+n, cmp1); 
        else 
            sort(node, node+n, cmp2);
        //输出按分数排序后的结果
        for(int i=0;i<n;i++)
            cout<<node[i].name<<' '<<node[i].score<<endl;
    }
    return 0;
}

利用unordered_map计数，并按输入顺序输出

原题链接

题目大意：统计每个候选人的得票数。

输入有4行。第1行表示候选人数n；第2行表示n个候选人的名字；第3行表示投票人数m；第4行表示m个投票结果，其中有些是废票，需要单独统计。最后按照录入顺序，输出每个候选人的得票，以及废票的数量。

输入：
4
A B C D
8
A D E CF A GG A B
输出：
A : 3
B : 1
C : 0
D : 1
Invalid : 3

分析

一一映射的题目，肯定用map啊：

1	map<候选人, 得票>

不要求排序，所以用unordered_map，但是unordered_map不保证遍历顺序就是插入顺序，所以额外用vector记录一下插入的顺序。

代码

#include<iostream>
#include<unordered_map>
#include<string>
#include<cstring>
#include<vector>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        unordered_map<string, int> candidates;
        //unordered_map不保证遍历顺序就是插入顺序，所以用vector来保存插入顺序
        vector<string> vec;  
        string s;
        for(int i=0;i<n;i++){
            cin>>s;
            candidates[s] = 0;  //初始时，各候选人得票都是0
            vec.push_back(s);
        }
        int m;
        int invalid = 0;
        cin>>m;
        for(int i=0;i<m;i++){
            cin>>s;
            //候选人存在，计数+1
            if(candidates.find(s) != candidates.end())
                candidates[s] ++;
            //候选人不存在，无效票+1
            else
                invalid ++;
        }
        //打印候选人及其得票
        for(int i=0;i<n;i++)
            cout<<vec[i]<<" : "<<candidates[vec[i]]<<endl;
        cout<<"Invalid : "<<invalid<<endl;
    }
    return 0;
}

Gwofoo's blog

【OJ】刷题记录2021-12