(总结篇))
- ###以四道题来总结
题号: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; }
