洛谷3411 - 序列变换

题意

给定一个长度为N的数列Ai。
你可以对数列进行若干次操作,每次操作可以从数列中任选一个数,把它移动到数列的开头或者结尾。
求最少经过多少次操作,可以把数列变成单调不减的。“单调不减”意味着数列中的任意一个数都不大于排在它后边的数。

分析

你可以把题意转化为:找到一个不降子序列,使得未选中的数必须不处于子序列的最小值和最大值之间(理由:小于等于最小值的可以移到前面去,大于等于最大值的可以移到后面去)
即找到一个值的区间[L, R],在其中选择一个不降子序列,使得其包含了区间(L, R)中的所有值。
[L, R]表示闭区间,(L, R)表示开区间!)

那么你只要维护一个答案队列,使得其满足题意。每次考虑扩展右区间,同时检查可行性,更新最优解。
需要注意的是,新增的节点值相同时可能会互相产生干扰,我们应当考虑倒序检查,之后顺序入队。

代码 & 注释

(使用了C++11新语法,请加上--std=c++11编译)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// ==============================
// author: memset0
// website: https://memset0.cn
// date: 2018.08.07 14:22:32
// ==============================
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int read() {
int x = 0; char c = getchar(); bool m = 0;
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') c = getchar(), m = 1;
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 1e6 + 10;
int n, m, l, r, cnt, ans, a[maxn], q[maxn];
vector < int > b[maxn];

int main() {
n = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
b[a[i]].push_back(i);
m = max(m, a[i]);
}
l = 1, r = 0;
for (int i = 1; i <= m; i++)
if (b[i].size()) {
cnt = 0;
for (auto it = b[i].rbegin(); it != b[i].rend(); it++) {
// 反向更新,避免值相同的数产生影响
int i = *it;
while (l <= r && q[r] > i) {
// 进入while循环说明发现当前节点不能直接加入到答案队列中
// 但由前面可知要使答案有效所去的数必须连续
// 那么删除答案队列的末尾使得当前节点可以被加入
while (l <= r && a[q[l]] < a[q[r]])
l++; // 如果删除当前的R可能导致答案队列不能使得值域连续
// 这样的话只能删除答案队列里之前的值
r--; // 删除答案队列里的末尾值
}
cnt++;
ans = max(ans, r - l + 1 + cnt);
// 请不要写 ans=max(ans,r-l+1+(++cnt)),否则 WA 40 分等着你!
}
for (auto it = b[i].begin(); it != b[i].end(); it++)
q[++r] = *it; // 加入到答案队列中
}
printf("%d\n", n - ans);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×