对于模拟题，我们只需要考虑两个事情，1 怎么存数据 2 怎么模拟

round()四舍五入

count() 哈希表中查找是否存在，存在为1

容器中升降序排序

  1. sort(Array.begin(),Array.end(),greater<类型>());  //降序
  2.     sort(Array.begin(),Array.end(),less<类型>());   //升序
  4. 或者自定义cmp函数
  5. bool cmp(int a,int b){
  6.     return a>b;
  7. }
  8. sort(p[i].begin(),p[i].end(),cmp);

当使用getline读入一行时，如果前面有cin，需要使用getchar()吞掉上一个回车

getline配合stringstream可以遍历以空格为分隔的一串字符串

  1. 输入a b c d
  2. string line;
  3. getline(cin,line);
  4. string key;
  5. stringstream ss(line);
  6. while(ss>>key)

s = ss.substr(index); 截取ss字符串index位置后的字符串给s

结构体排序 重载操作符

  1. struct Student{
  2.     string id;
  3.     int score;
  4.     int position;
  5.     int localrank,allrank;
  6.     bool operator<(const Student& t)const{
  7.         if(score!=t.score) return score>t.score;
  8.         else return id<t.id;
  9.     }
  10. }

定义结构体后记得写 ;

堆排序

如何手撸一个堆？
首先，堆是一个完全二叉树，且分为小根堆（子节点小于父母节点）和大根堆（子节点大于父母节点）。
那用什么来存入一个堆呢？一维数组！
对于一个一维数组a[] ，n[1]表示根节点，a[2n]和a[2n+1]分别为a[n]的左右子节点。
对于一个堆来说，我们有两个操作，down()操作和up()操作，这两个操作的组合（时间复杂度均为logn）可以实现对堆的一切修改。
对于小根堆:
down()操作：将某一个节点的值变大，堆重新调整，该节点下移
up()操作：将某一个节点的值变小，堆重新跳整，该节点上移
image.png
堆排序：每次输出堆顶
image.png

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 100010;
  4. int h[N],size_;
  5. int n,m;
  6. void down(int u){
  7.     int t = u;
  8.     if(2*u<=size_&&h[t]>h[2*u]) t = 2*u;
  9.     if(2*u+1<=size_&&h[t]>h[2*u+1]) t = 2*u+1;  //两个if找出三个节点中最小的节点，用这个节点和父节点交换
  10.     if(u!=t){
  11.         swap(h[u],h[t]);
  12.         down(t);
  13.     }
  14. }
  15. int main(){
  16.     cin>>n>>m;
  17.     for(int i=1;i<=n;i++){
  18.         int k;
  19.         cin>>k;
  20.         h[i] = k;
  21.     } 
  22.     size_ = n;
  23.     for(int i=n/2;i;i--) down(i);
  24.     while(m--){
  25.         cout<<h[1]<<' ';
  26.         swap(h[size_], h[1]);
  27.         size_--;
  28.         down(1);
  29.     }
  30.     return 0;
  31. }

二分

二分模板 1.循环必须是l < r 2.if判断条件看是不是不满足条件， 然后修改上下界 3.若if else后是r = mid - 1，则前面mid 语句要加1 4.出循环一定是l == r，所以l和r用哪个都可以

二分只有下面两种情况
1：找大于等于给定数的第一个位置 （满足某个条件的第一个数）
2：找小于等于给定数的最后一个数 （满足某个条件的最后一个数）

image.png
image.png

  1. // 判断条件很复杂时用check函数，否则if后直接写条件即可
  2. bool check(int mid) {
  3.     ...
  4.     return ...;
  5. }
  7. // 能二分的题一定是满足某种性质，分成左右两部分
  8. // if的判断条件是让mid落在满足你想要结果的区间内
  10. // 找满足某个条件的第一个数  即右半段
  11. int bsearch_1(int l, int r)
  12. {
  13.     while (l < r)
  14.     {
  15.         int mid = l + r >> 1;
  16.         if (check(mid)) r = mid;  
  17.         else l = mid + 1;
  18.     }
  19.     return l;
  20. }
  22. // 找满足某个条件的最后一个数  即左半段
  23. int bsearch_2(int l, int r)
  24. {
  25.     while (l < r)
  26.     {
  27.         int mid = l + r + 1 >> 1;
  28.         if (check(mid)) l = mid;
  29.         else r = mid - 1;
  30.     }
  31.     return l;
  32. }
  35. 注释：
  36.  模板2求mid时要加一，因为除以2默认是下取整
  37.  比如红色区域二分到l = 3， r = 4，目标位置是4，那么 若不加一,则mid永远无法到4