(10条消息) 蓝桥杯 I.双向排序_Jozky86的博客-CSDN博客_蓝桥杯双向排序
#include #include #include #include #include #include #include<string> #include #include #include<set> #include #include #define ll long long #define PII pair using namespace std; const int INF = 0x3f3f3f3f; //为了memset()可以用 const double eps = 1e-7; const double pi = acos(-1.0); inline ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } //gcd(0,a)=a inline ll _max(ll a, ll b) { return a > b ? a : b; } static const int N = 100010; //vector >ord; PII<int, int> ord[N]; //++top模式，0号元素没有值 static int ans[N]; static int n, m, a, b; void solve() { cin >> n >> m; // 原数组就是1~n int top = 0; // 压缩调整次数 while(m--) { //处理order cin >> a >> b; if (!a) { //order 1 if (top && ord[top].first == 0) b = max(ord[top--].second, b); while (top >= 1 && b >= ord[top-1].second) top -= 2; ord[++top] = { 0,b }; } else if (top) { //保证前面一定有一个order 1，然后才输入order 2 if (ord[top].first == 1) b = min(ord[top--].second, b); while (top >= 1 && b <= ord[top - 1].second) top -= 2; ord[++top] = { 1,b }; } } int l = 1, r = n, v = n; for (int i = 1; i <= top; ++i) { //到top为止，避免访问已被覆盖的元素，当然也可以用vector if (ord[i].first == 0) while (r > ord[i].second && r > l)ans[r--] = v--; else while (l l) ans[l++] = v--; } // 对中间进行处理 if (top % 2)//最后一次排序为升序 while (l <= r)ans[l++] = v--; else //最后一次排序为降序 while (l <= r)ans[r--] = v--; for (int i = 1; i <= n; ++i)printf("%d ", ans[i]); } signed main() { solve(); return 0; }