CF1888D Dances 题解

FFTotoro · 2023-10-23 21:02:34 · 题解

前言

该题解中 D2 做法基于 D1 的做法。

解法

Easy Version

先考虑如果数组最终大小 k 确定怎么判断答案是否合法：有一个显然的贪心，把 a 数组中最大的 n-k 个移除，把 b 中最小的 n-k 个移除，排序后进行比较所有 a_i 与 b_i 的大小关系即可。

再观察到 k 具有单调性，直接二分即可。

Hard Version

一开始想到一个巨大麻烦的分段讨论 a_1 值的做法，但是因为巨难调放弃了。

再考虑每次只修改第一个数有什么性质：直觉告诉我们对答案的影响不大，猜测其不超过 1。事实上这是正确的，感性理解一下，即修改一个数后，不管修改为多少，a 数组中一些元素排名变动不超过 1，这时如果 a 数组因为这个事没法像原来一样与 b 形成合法的序列，那么 a 与 b 各再删一个即可。

设 a_1=1 的时候答案为 x，则在 a_1 大于某个临界点 y 时答案为 x+1。显然这个 y 也可以二分，于是二分套二分判断中点 a_1=m 时的答案是否等于 l 即可，内部套的那个二分就是 D1 做法。答案为 xy+(x+1)(m-y)。时间复杂度 O(n\log n\log m)。

放代码（Hard Version）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,m; cin>>n>>m;
    vector<int> a(n),b(n),c(n);
    a[0]=1; for(int i=1;i<n;i++)cin>>a[i];
    for(auto &i:b)cin>>i;
    c=a,sort(a.begin(),a.end()); // 记得备份
    sort(b.begin(),b.end());
    auto pd=[&](int x){
      vector<int> p,q;
      for(int i=0;i<x;i++)
        p.emplace_back(a[i]);
      for(int i=n-x;i<n;i++)
        q.emplace_back(b[i]);
      for(int i=0;i<x;i++)
        if(p[i]>=q[i])return false;
      return true;
    }; // 内部二分
    auto f=[&](int x){
      a=c,a[0]=x;
      sort(a.begin(),a.end());
      int l=0,r=n;
      while(l<r){
        int m=l+r+1>>1;
        if(pd(m))l=m;
        else r=m-1;
      }
      return l;
    }; // 求当 a[1]=x 时的最大数组大小
       // 真正答案要用 n 减去它
    int l=f(1),l2=1,r2=m;
    while(l2<r2){
      int m2=l2+r2+1>>1;
      if(f(m2)==l)l2=m2;
      else r2=m2-1;
    } // 内部二分
    cout<<l2*(n-l)+(m-l2)*(n-l+1)<<'\n'; // 计算答案
  }
  return 0;
}