蓝桥杯 历届真题 双向排序【第十二届】【省赛】【C组】
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
改了半天只有60分，还是超时，还不知道怎么写，后面再看吧┭┮﹏┭┮
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+10;
int n,m,t,d;
int a[N],b[N];
string s;
signed main(){cin>>n>>m;for(int i=0;i<n;i++){a[i]=i+1;}int p,q,last_0=0,last_1=n;int flag=-1;for(int i=0;i<m;i++){cin>>p>>q;if(i==0){if(p==0){last_0=q;flag=0;}else{last_1=q;flag=1;}}else{if(p==0){if(flag==1){sort(a+last_1-1,a+n);last_1=n; }last_0=max(last_0,q);flag=0;}else{if(flag==0){sort(a,a+last_0,greater<int>());last_0=0; }last_1=min(last_1,q);flag=1; }}}if(flag==0){sort(a,a+last_0,greater<int>());}else{sort(a+last_1-1,a+n);}for(int i=0;i<n;i++){cout<<a[i]<<" ";}return 0;
}看别人代码发现自己只考虑了两种情况：
一、输入为连续的0，那么最大的q生效，作为排序右边界；
二、输入为连续的1，那么最小的q生效，作为排序左边界；
还应该有：
- 交替输入且第一次输入0，第二次1，第三次0，且第三次q比第一次大，那么前两次作废；
- 交替输入且第一次输入1，第二次0，第三次1，且第三次q比第一次小，那么前两次作废；