CF1773E Easy Assembly 题解

FFTotoro · 2022-12-10 18:01:09 · 题解

本题需要使用离散化算法。

因为本题我们只关注数的相对大小，先对塔里面的数进行离散化处理。即，按照从小到大的顺序编号为 1,2,3\ldots。

然后，如果对于一个塔 a，塔里存在 a_i-a{i+1}\ne 1，那么这两个元素之间就必须进行一次分裂操作（不妨设 a_i<a_{i+1}，因为存在 a_i<k<a_{i+1}，而 k 在最后必须插入它们之间，如果不进行分裂无法插入）。

因为所有数皆不相同，所以不存在两个塔分别是 \{1,2\} 和 \{2,1\} 导致无法合并的情况，上述的做法是正确的。

记分裂的次数为 c，那么分裂完成后总共就有 c+n 个塔，所以共需 c+n-1 次合并。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n,c=0,c0=0; cin>>n;
  vector<vector<int> > a(n);
  set<int> s; map<int,int> m;
  for(auto &i:a){
    int k; cin>>k; i.resize(k);
    for(auto &j:i)cin>>j,s.emplace(j); // 记录
  }
  for(auto &i:s)m[i]=++c; // 编号
  for(auto &i:a)for(auto &j:i)j=m[j]; // 赋值
  for(auto &i:a)
    for(int j=1;j<i.size();j++)
      if(i[j]-i[j-1]>1||i[j]-i[j-1]<0)c0++; // 判断
  cout<<c0<<' '<<c0+n-1<<endl;
  return 0;
}