STL(八)(总结篇)

• ###以四道题来总结

---

题号:lanqiao OJ 3226

1.宝藏排序II

• ?### 这道题主要考察sort,非常简单输出就是升序不需要自定义比较函数

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
//这里用int就足够了不需要开long long
int a[N];
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){
    cin>>a[i];
  }
  //默认就是升序不需要自定义比较函数
  sort(a+1,a+1+n);
  //直接输出
  for(int i=1;i<=n;++i){
    cout<<a[i]<<' ';
  }
  return 0;
}

---

题号:lanqiao OJ 3225

宝藏排序I

?这段是宝藏排序I的代码:除了数据范围并无不同

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int a[N];
int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;++i){
    cin>>a[i];
  }
  sort(a,a+n);
  for(int i=0;i<n;++i){
    cout<<a[i]<<' ';
  }
  return 0;
}

---

题号:lanqiao OJ 1624

2.小蓝吃糖果

• ??### 这道题主要考察poriority_queue优先队列
• ?一定要满足 总的糖果数量减去最多糖果数的数量要大于最多糖果数的数量-1 这是最低条件
• 核心思想:先找出最多的糖有mx个,那么要插的空隙就有mx-1个

#include<bits/stdc++.h>
using ll=long long;
using namespace std;
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  priority_queue<int> pq;
  ll sum=0,x;
  for(int i=1;i<=n;++i){
    cin>>x;
    pq.push(x);
    sum+=x; //这里是糖果的总数
  }
  //这里就可以求出mx最大值
  ll mx=pq.top();

  if(sum-mx>=mx-1){
    cout<<"Yes"<<"\n";
  }
  else{
    cout<<"No"<<"\n";
  }
  return 0;
}

---

?题号:lanqiao OJ 2490

3.小蓝的括号串1

• ??### 这道题主要考察stack
• 核心思想:左括号与右括号完美相消,遇到左括号入栈,遇到右括号出栈

#include<bits/stdc++.h>
using namespace std;
const int N=105;
stack<char> stk;
char s[N];
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  cin>>s+1;
  bool ans=true;
  for(int i=1;i<=n;++i){
    //是左括号入栈
    if(s[i]=='('){
      stk.push(s[i]);
    }
    //右括号
    else{
      //stk中有东西且栈首为左括号就出栈
      if(stk.size()&&stk.top()=='('){
        stk.pop();
      }
      //否则不对
      else{
        ans=false;
      }
    }
  }
  //都消完了栈里还有左括号也不对
  if(stk.size()){
    ans=false;
  }
  cout<<(ans?"Yes":"No")<<"\n";
  return 0;
}

---

?题号:lanqiao OJ 1531

4.快递分拣

?

• ??### 这道题主要考察map,vector,string的综合运用
• 单号和城市都可以用string类型存储

#include <bits/stdc++.h>
using namespace std;

map<string,vector<string>> mp;

vector<string> citys;

int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;++i){
    string a,b;
    cin>>a>>b;
    //已经有了该城市
    if(!mp.count(b)){
      citys.push_back(b);
    }
    mp[b].push_back(a);
  }
  //遍历城市
  for(const auto&city:citys){
    cout<<city<<' '<<mp[city].size()<<"\n";
    //遍历单号
    for(const auto&i:mp[city]){
      cout<<i<<"\n";
    }
  }
  return 0;
}