D. Unmerge
题目链接
题目：
判断是否存在长都为n的两个数组 a[ ] , b[ ]
每次 ：
如果 a 的第一个元素 小于 b的第一个元素
就把 a的第一个元素 存到 c 中 ，然后 a 的第一个元素弹出
反之 就把 b的第一个元素 存到 c 中 ，然后 b 的第一个元素弹出
最后得到了一个数组 c [ ]
题目给你一个数组c , 问是否存在数组 a[] , b[] ， 是就输出 YES
大家模拟一下就可以把题目转化成：
从 c 的第一个元素开始 ，当前位置为i , 找 距离最近的 比当前数大的数的位置 pos( 用单调栈 )
然后 c[ i ~ pos - 1] 这段且要么在 a[] ， 要么在 b[]
于是我们把c数组分成很多个块 ， 然后进行分配 ， 判断是否可以使得刚好分配均匀（a[] 、b[] 长度为n）
我的做法是：
① 单调栈判断 距离最近的 比当前数大的数的位置 pos
② 进行分块 ， 用 vec 记录分块的大小
③ 判断是否有几块加起来等于 n (代码是 n / 2 因为我一开始 n *= 2)
详细看代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 2e6 + 10; #define ll long long #define ios std::ios::sync_with_stdio(false) #define int long long template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);} #define pb(a) push_back(a) #define cn cout << ' ' int a[maxn]; int pos[maxn]; ///记录距离最近的 比a[i]大的数的位置 int sta[maxn]; ///单调栈 int cnt = 0; vector<int> vec;///存块 int dp[maxn];///dp[i]表示dp[i]出现过了吗 ， 出现了几次 map<int , int> ma; ///ma[x] 代表 x 本次出现的次数 ， 往下看 signed main() { ios,cin.tie(0); int t; read(t); while(t --){ ma.clear(); vec.clear(); cnt = 0; int n; read(n); n *= 2; for(int i = 1 ; i <= n ; i ++) read(a[i]) , dp[i] = 0 , pos[i] = 0; for(int i = 1 ; i <= n ; i ++){ while(a[sta[cnt]] < a[i] && cnt > 0){///单调栈 pos[sta[cnt --]] = i; } sta[++ cnt] = i; } for(int i = 1 ; i <= n ; i ++){ if(pos[i] == 0){///如果是最大的数 ， 因为我最大的数肯定留在栈底出不来， 所以他的pos = 0 vec.pb(n - i + 1);///i ~ n 这一大块 break; } else{ vec.pb(pos[i] - i);///i ~ pos[i- 1] i = max(i , pos[i] - 1);///i 跳一下 } } //for(int i = 0 ; i < vec.size() ; i ++) cout << "sb : " << vec[i] << ' '; for(int i = 0 ; i < vec.size() ; i ++){///判断若干个vec[i]能不能组成 n / 2 if(dp[n / 2])break; if(vec[i] > n / 2) break; dp[vec[i]] ++; ma.clear(); ma[vec[i]] ++; /// 本次出现了vec[i] for(int j = 1 ; j <= n / 2 ; j ++){ if(dp[j] > ma[j] && dp[j] > 0){/// 如果j总共出现的次数大于本次出现的次数 ///也就是在取当前数之前，这个dp[j]就 > 0 了 ， 这样不会重复计算 dp[j + vec[i]] ++;///那 j + vec[i] ma[j + vec[i]] ++; } } } if(dp[n / 2]) cout << "YES "; else cout << "NO "; } return 0; }
最后一段还可以简化一下（感谢G爷）：
