🌓
Ftt2333's Nest

ARC114F

创建于 2022-11-10

Tags: OI

Categories: OI

@wsyear强无敌,模拟赛场切黑题。

题目大意

给你一个长度为 nn 的排列,Alice 先会把它分成 mm 段。

然后 Bob 会把这 mm 段重新排列,而每段内部位置不变。

Alice 希望这个序列字典序最小,而 Bob 希望这个序列字典序最大。

输出重排后的序列。

解题思路

考虑贪心。

我们发现字典序一定不会比原来的序列小,所以我们要让不变的前缀尽量长。

很明显这个前缀的长度是有单调性的,所以可以考虑二分。

判断是否可行:

假设你现在二分到的长度是 lenlen

我们分的 mm 段中有两种,一种是在 [1,len][1,len] 中的,一种是在 [len+1,n][len+1,n] 中的。

对于在 [1,len][1,len] 中的段,我们发现他们的开头是单调递减的,否则Bob可以把开头较大的移动到前面。

对于 [len+1,n][len+1,n] 的段,每一段的开头都要比 [1,len][1,len] 中的开头小,否则你可以把开头大的移到前面。

考虑枚举 [1,len][1,len] 中的段数 xx,然后求出最后一段开头的最大值 valval,那么只要找出 [len+1,n][len+1,n] 中有多少个数(假设有 yy 个)可以作为开头(也就是小于 valval),如果 x+ymx+y\ge m 那么就可行。

接下来要求出 valval

这里的思路参考了 P4577 [FJOI2018]领导集团问题 的思路。

维护一个set,从大到小排,其中第 ii 个元素表示长度为 ii 的递减子序列的最大结尾。

考虑加入一个数 xx,那么找到他的后继 yy,发现以 xx 结尾和以 yy 结尾的最长下降子序列长度是一样的,而 x<yx<y,所以可以把 yy 删除。

现在求出了最长的不变的前缀 lenlen,我们现在就只要考虑 [len+1,n][len+1,n] 应该怎么分比较好。

首先你在 [len+1,n][len+1,n] 分的段数一定是越少越好的,而这个段数在check的时候就可以求出来了。

显然你要取最小的前几个一定是最优的,这样才能保证重排后 len+1len+1 的位置数最小。

这样就做完了。

代码示例

不是很清除,凑和着看吧:

/*
* @Author: ftt2333
* @Email: ftt2333@126.com
* @Last Modified time: 2022-11-10 10:50:00
*/

#include <bits/stdc++.h>
using namespace std;
#define off ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fin(s) freopen(s, "r", stdin)
#define fout(s) freopen(s, "w", stdout)
#define fio(s) fin(s".in"), fout(s".out")
using ll = long long; using ull = uint64_t;
using lll = __int128; using ulll = __uint128_t;
using db = double; using ldb = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using vi = vector<int>; using vl = vector<ll>;
using uchar = unsigned char; using uint = unsigned int;
template<class T> using uid = uniform_int_distribution<T>;
template<class T> using urd = uniform_real_distribution<T>;
#define rep(i, a, b) for(auto i = (a); i <= (b); i++)
#define per(i, a, b) for(auto i = (a); i >= (b); i--)
#define go(i, h, e, x) for(int i = h[x]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define szof(a) ((int)(a).size())
#define mem(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))

mt19937 rnd(random_device{}());
const int mod = 998244353, N = 2e5 + 10;
int a[N], n, m, sum[N], id[N];
bool vis[N];

int check(int len) {
  set<int> s;
  rep(i, 1, len) {
    if(a[i] > a[1]) continue;
    auto it = s.upper_bound(a[i]);
    if(it != s.begin()) s.erase(--it);
    s.insert(a[i]);
  }
  rep(i, 1, n) sum[i] = 0;
  rep(i, len + 1, n) sum[a[i]]++;
  rep(i, 2, n) sum[i] += sum[i - 1];
  int j = szof(s);
  for(auto x: s) {
    if(j + sum[x] >= m) return j;
    j--;
  }
  return 0;
}

int main() {
  off;
  cin >> n >> m; rep(i, 1, n) cin >> a[i], id[a[i]] = i;
  int l = 0, r = n;
  for(; l < r; ) {
    int mid = l + r + 1 >> 1;
    if(check(mid)) l = mid;
    else r =  mid - 1;
  }
  int res = m - check(l);
  vi heads; heads.pb(1);
  if(1 > l) res--;
  rep(i, 1, n) if(res && id[i] != 1 && id[i] > l) heads.pb(id[i]), res--;
  sort(all(heads), [&](int x, int y) {
    return a[x] > a[y];
  });
  for(int x: heads) vis[x] = 1;
  for(int x: heads) {
    cout << a[x] << ' ';
    int i = x + 1;
    for(; i <= n && !vis[i]; i++) cout << a[i] << ' ';
  }
}

Powered by Hexo, theme by Facter