CF 631C. Report
题目描述:给你n个数每次排前m个数（可能降序可能升序）问你最后出来是什么样子的；
分析：它的顺序只跟后面最大的m有关 比如3 4 那么前三个不管怎么排对我排前4个都没影响
总结下这种规律题，首先多用电脑去找规律 ，也就是打表，其次一般都有很多条件什么的，找规律也就是把条件逐一合并，到最后容易实现
ac代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int ,int> P;
int a[200004];
int b[200004];
int main(){
// freopen("1.txt","r",stdin);
int n,m;
cin>>n>>m;
vector<P> sta;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
while(!sta.empty()&&sta.back().second<=y) sta.pop_back();
sta.push_back(make_pair(x,y));
}
if(m!=1||sta[0].first==1)sort(a+1,a+sta[0].second+1,less<int>());
else sort(a+1,a+sta[0].second+1,greater<int>());
for(int i=1;i<=sta[0].second;i++)b[i]=a[i];
int mi=1,ma=sta[0].second;
if(m!=1)for(int i=0,sz=sta.size();i<sz;i++){
if(i==sz-1){
if(sta[i].first==1) for(int j=1;j<=sta[i].second;j++) a[j]=b[mi++];
else for(int j=1;j<=sta[i].second;j++) a[j]=b[ma--];
break;
}
int r=sta[i].second,flag=sta[i].first,l=sta[i+1].second;
for(int j=r;j>l;j--)
if(flag==1) a[j]=b[ma--];
else a[j]=b[mi++];
}
for(int i=1;i<=n;i++){
cout<<a[i];
if(i!=n)cout<<' ';
else cout<<endl;
}
}
美团成长空间 2667人发布
查看28道真题和解析