CF1906E Merge Not Sort

FFTotoro · 2023-12-07 21:53:20 · 题解

考虑怎样的一段数一定要被绑在一块（即一定要在同一个序列并且相邻），我们可以通过如下的方式来寻找这样的一段：

扫一遍输入序列 c，对于一个数，如果是新扫到的，那么将它作为块头，一直往右扫直到扫到比它大的就停止，比它大的那个作为另一个块的块头……以此往复。

这样做显然是正确的。因为如果一个块的任意一个非块头元素放到另一个序列都会被先放到 c。

然后把所有块打包起来，看能不能把块往 a,b 里放使得 a,b 的大小都为 n。这一部分做一个背包即可，中间借助 std::set 构造方案。

最后记得对于最终序列中的每一个块按照块头元素大小升序排序。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n,l=0; cin>>n;
  vector<int> c(n<<1);
  for(auto &i:c)cin>>i;
  vector<int> h=c,s(n<<1);
  for(int i=1;i<n<<1;i++)
    if(h[i]<h[i-1])h[i]=h[i-1],s[i-1]=1;
    // 标记一下位置
  vector<vector<int> > w,a,b;
  while(l<n<<1){
    vector<int> v;
    while(l<n<<1&&s[l])
      v.emplace_back(c[l++]);
    v.emplace_back(c[l++]);
    w.emplace_back(v);
  } // 把所有块找出来
  vector<set<int> > f(n+1);
  for(int j=0;j<w.size();j++)
    for(int i=n-1;~i;i--)
      if(!i||!f[i].empty()){
        if(i+w[j].size()<=n&&f[i+w[j].size()].empty()){
          for(int k:f[i])f[i+w[j].size()].emplace(k);
          f[i+w[j].size()].emplace(j);
        }
      } // 背包 DP，构造
  if(f[n].empty()){cout<<"-1\n"; return 0;}
  for(int i=0;i<w.size();i++)
    if(f[n].find(i)==f[n].end())b.emplace_back(w[i]);
    else a.emplace_back(w[i]); // 分配到 2 个序列
  sort(a.begin(),a.end()); // 对块进行排序
  sort(b.begin(),b.end());
  for(auto i:a)for(int j:i)cout<<j<<' ';
  cout<<endl; // 直接遍历输出
  for(auto i:b)for(int j:i)cout<<j<<' ';
  cout<<endl;
  return 0;
}