牛客算法竞赛入门课第二节习题Part1（Laptop~ 分数线划定）(UP:吐泡泡)
牛客算法竞赛入门课第二节习题 Part1
必知：sort用法https://www.cnblogs.com/program-ai-cv-ml-se-fighting/p/11924550.html
##update：吐泡泡
思路：
用栈模拟一下就好，但是要注意当两个小泡泡合成大泡泡时是否会有两个大泡泡消除。
另外本题是多组输入。
代码：
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43860424&returnHomeType=1&uid=115850812
1.Laptop
思路：（sort排序+枚举）
用结构体存储一下属性，sort排序后直接两层for枚举。
对于每一台笔记本，我们只需要找到一个m,s都比他大的笔记本即可，所以在内层循环可以从大到小循环，遇到完虐他的直接break内层循环即可。
如果条件再多的话，也可以考虑用线段树/树状数组/RMQ过。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
struct node{
int m,s;//结构体存储信息
}a[maxn];
int n;
bool cmp(node a,node b){//二维偏序排序
if(a.m==b.m) return a.s<b.s;
return a.m<b.m;
}
int main(){
///输入信息
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].m>>a[i].s;
}
//排序
sort(a+1,a+1+n,cmp);
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=n;j>i;j--)
if(a[i].s<a[j].s&& a[i].m <a[j].m){//编号为u的笔记本电脑被完虐，计数后跳出循环即可
cnt++;
break;
}
}
cout<<cnt<<endl;
return 0;
} 2 .大吉大利，今晚吃鸡
思路：（递归）
仿照汉诺塔的思路即可，但是本题是 限定圆盘只能够移动到相邻的柱子
所以
void dfs(char a,char b,char c,int n){
if(!n) return ;///n==0 所有盘子都已经被转移 递归结束
dfs(a,b,c,n-1);///把n-1个盘子从b移动到c
cnt++;//把第n个从a移动到b
dfs(c,b,a,n-1);///把n-1个盘子从b移动到a
cnt++;//把第n个盘子从b移动到c
dfs(a,b,c,n-1);//把n-1个盘子从b移动到c
} 代码：
#include<bits/stdc++.h>
using namespace std;
int cnt=0;
void dfs(char a,char b,char c,int n){
if(!n) return ;
dfs(a,b,c,n-1);cnt++;
dfs(c,b,a,n-1);cnt++;
dfs(a,b,c,n-1);
}
int main(){
int n;
while(cin>>n){
cnt=0;
dfs('a','b','c',n);
cout<<cnt<<endl;
}
return 0;
} 3.简单的数据结构
思路：（stl之vector的使用）
对应题意说一下几个操作，记vector为v
0 .
v.begin() 返回指向容器最开始位置数据的指针
v.end() 返回指向容器结束位置数据的指针
1.
在v的开头插入元素 v.insert()
v.insert(v.begin(),8);//在最前面插入新元素,此时v为8 2 7 9 5 v.insert(v.begin()+3,1);//在迭代器中下标为3的元素前插入新元素,此时v为8 2 7 1 9 5 v.insert(v.end(),3);//在向量末尾追加新元素,此时v为8 2 7 1 9 5 3 v.insert(v.end(),3,0);//在尾部插入3个0,此时v为8 2 7 1 9 5 3 0 0 0
2.
v.erase(it);///it为迭代器类型 //表示删除容器里it所指位置的元素
3.
正常的vector插入就是在尾部插入，v.push_back(x)即可。
4.
pop_back()可以删除最后一个元素.
5.
reverse函数会将一段区间内的数逆转
6.
v.size()表示容器大小；
for(auto tt:v) 表示按照顺序依次从v中取出元素tt
7.
sort即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
vectorv;
int n,m;
cin>>n>>m;
while(m--){
int op;cin>>op;
if(op==1){
int w;cin>>w;
v.insert(v.begin(),w);
}
else if(op==2){
v.erase(v.begin());
}
else if(op==3){
int w;cin>>w;
v.push_back(w);
}
else if(op==4){
v.pop_back();
}
else if(op==5){
reverse(v.begin(),v.end());
}
else if(op==6){
cout<<v.size()<<endl;
for(auto tt:v){
cout<<tt<<" ";
}
puts("");
}
else sort(v.begin(),v.end());
}
return 0;
} 4.栈和排序
思路：（栈+优先队列）
字典序最大即是要尽可能的要按照n,n-1,n-2的顺序。
所以当能够这样时，我们要尽可能这样。
可以将数放到大根堆里，然后逐个与数组里的数比较，如果当前数组里的数是最大值的话直接输出即可，否则就放到栈内，最后进行输出。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int a[maxn];
int main(){
int n;scanf("%d",&n);
priority_queue q;
stackstk;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
q.push(a[i]);
}
for(int i=1;i<=n;i++)
if(a[i]==q.top()) printf("%d ",q.top()),q.top();
else stk.push(a[i]);
while(stk.size()){///栈非空
printf("%d ",stk.top());
stk.pop();
}
return 0;
} 5.竞赛技巧
思路：（sort排序）
可以在输入的时候将时间化成秒，排序的时候直接按总和排；
也可以排序的时候逐个比较。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=5100;
struct node{
int h,m,s;
int sum;
}a[maxn];
bool cmp1(node a,node b){
return a.sum<b.sum;
}
bool cmp2(node a,node b){
if(a.h==b.h&&a.m==b.m) return a.s<b.s;
if(a.h==b.h) return a.m<b.m;
return a.h<b.h;
}
int main(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>a[i].h>>a[i].m>>a[i].s;
a[i].sum=a[i].h*60*60+a[i].m*60+a[i].s;
}
/// sort(a+1,a+1+n,cmp1);
sort(a+1,a+1+n,cmp2);
for(int i=1;i<=n;i++)
cout<<a[i].h<<" "<<a[i].m<<" "<<a[i].s<<endl;
return 0;
} 6.老子的全排列呢
思路：（dfs 或全排列函数）
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=10;
int main(){
int a[8]={1,2,3,4,5,6,7,8};//初始化数组
do{
for(int i=0;i<8;i++){//输出
cout<<a[i];
if(i==7) puts("");
else cout<<" ";
}
}while(next_permutation(a,a+8));///全排列函数，将指定区间的数组进行全排列，也可用dfs实现
return 0;
} 7.逆序数
思路：（归并排序或树状数组）
代码：(直接搬的很久以前写的代码0.0)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
int a[N],t[N];
ll f(int a[],int l,int r){
if(l>=r) return 0;
int mid = (l + r)/2 ;
ll res = f(a,l,mid) + f(a,mid + 1 ,r);
int k = 0,i = l,j = mid + 1;
while(i <= mid && j <= r)
if(a[i] <= a[j]) t[k++]=a[i++];
else{
res += mid - i + 1;
t[k++] = a[j++];
}
while(i <= mid) t[k++] = a[i++];
while(j <= r) t[k++]= a[j++];
for(i = l,j = 0;i <= r;i++,j++) a[i]=t[j];
return res;
}
int main(){
int n;
cin>>n;
for(int i = 0;i < n;i ++ ) scanf("%d",&a[i]);
cout<<f(a,0,n-1)<<endl;
}
8 .The Biggest Water Problem
思路：（递归+模拟）
代码：
#include<bits/stdc++.h>
using namespace std;
int cul(int n){
if(n<10) return n;//当n<10时结束递归
int sum=0;
while(n) sum+=n%10,n/=10;//得到各位数之和
return cul(sum);//返回结果
}
int main(){
int n;cin>>n;
cout<<cul(n)<<endl;
return 0;
} 9.小C的记事本
思路：（栈+字符串模拟）
代码：
#include<bits/stdc++.h>
using namespace std;
stackres;
int main(){
ios::sync_with_stdio(false);//读入写优化，加上这句只能用cin.cout;用scanf会WA！
int q;
while(cin>>q){
string s="";
while(q--){
int op;cin>>op;
if(op==1){
string tmp;cin>>tmp;
res.push(s);
s=s+tmp;//插入字符串
}
else if(op==2){
int k;cin>>k;
res.push(s);
s=s.substr(0,s.size()-k);//删除后k个字符
}
else if(op==3){
int k;cin>>k;
cout<<s[k-1]<<endl;//输出第k个字符，但是因为s的下标是从0开始，所以输出s[k-1]
}
else{
s=res.top();//res存储的是上一个状态
if(!res.empty()) res.pop();
}
}
while(!res.empty()) res.pop();
}
return 0;
} 10 .分数线划定
思路：（结构体排序）
注意如何求有多少人入选面试的方法，有可能那个分数线是好几个人同时拥有的，这时候人数就比m大了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
struct node{
int num,score;
}a[maxn];
int n,m;
bool cmp(node a,node b){//按照题目要求排序
if(a.score==b.score) return a.num<b.num;
return a.score>b.score;
}
int main(){
//输入
cin>>n>>m;
for(int i=1;i>a[i].num>>a[i].score;
//按照题目排序
sort(a+1,a+1+n,cmp);
int t=m*1.5;//假设人数
//特判相等人数
while(t<=n&&a[t].score==a[t+1].score) t++;
cout<<a[t].score<<" "<<t<<endl;
for(int i=1;i<=t;i++)///输出结果
cout<<a[i].num<<" "<<a[i].score<<endl;
return 0;
} 