CF1481E Sorting Books 超高质量题解
fanfansann
2021-02-18 11:17:11
## E - Sorting Books
一排书架上有 $n$ 本书排成一排,每本书上有一个颜色 $a_i$,你可以每次将一本书移动到书架的最右端,如果书架上的书,颜色相同的书都排到了一块,我们就认为他是漂亮的,请问将这个书架通过上面的那一种操作排成漂亮的书架,最少需要几次操作?
**Solution**
其实是超级简单的一道题 ~
首先根据题意,先不考虑最优解,我们直接全部往右乱扔就一定能满足,但是不一定是最优解,解决最优解问题,很明显要么贪心,要么DP,要么贪心 + DP。
首先考虑贪心策略,我们一上来最直观的感受就是,如果有一种颜色,没有完全在一块,中间参杂着其他颜色的书,但是这种颜色的书的数量非常非常的多,很明显我们就可以贪心地把这种颜色中间的书移走,这些这种颜色的书就会自动合并到一块,肯定比把这种颜色的很多很多的书一个一个丢到最右边要来的快,这一点很容易想到。
所以我们来尝试找一下,有没有这种颜色的书,或者好几种,只要区间不重叠就好,数量比它中间其他颜色的书的数量还要多,也就是找到若干个区间,但是直接找区间有点困难,题目只需要我们输出最少操作次数即可,所以在有了这个完美的贪心策略以后,我们考虑DP来模拟这个过程。
我们设 $f[i]$ 表示 $i\cdots n$ 区间里不需要移动的书的最大数量,很显然答案就是 $n-f[1]$。除去不需要移动的,把剩下的按照颜色的分类丢到右边就行了。
我们想要找到的是区间里书数量最多的颜色,并且可以是很多种区间不重叠的颜色,要先找区间,所以我们先存一下每种颜色的出现的左右区间 $l_i$ 和 $r_i$ ,因为要找数量最多的那一种,所以我们再使用 $cnt$ 数组存一下每种颜色出现的次数。因为现在考虑的是逆序 DP,所以再存一下 $\text cnt\_post_i$ ,表示的是 $i\cdots n$ 之间每种颜色的书的数量。
考虑转移方程:
(1)$\tt f\ [i] = \max\{f\ [i], f[i + 1]\}$
(2)$\tt f[i] = \max\{f [i], {cnt\_post} [ a[ i]]\}$
我们取 $i\cdots n$ 里当前最优的一种颜色,也就是只选择一个区间的情况。为什么不能写成 $\tt f[i] = \max\{f [i], {cnt\_post} [ a[ i]]+f[r[a[i]]+1]\}$ 呢,也就是为什么我们不能一块加上当前颜色区间右边的最优解呢?这样看上去好像没什么毛病呀?
参见样例:
```cpp
5
1 2 2 1 3
```
```cpp
2
```
会发现如果在没有完全完整的区间的基础之上更新,就会导致几个区间重叠,得到实际上是错误的 “最优解”
(3)当 $\tt l[a[i]]=i$时,$\tt f[i]=max\{cnt[a[i]]+f[r[a[i]]+1]\}$
这里我们已经完全走完了颜色 $\tt a[i]$ 的整个区间,可以跟其他区间合并以找到最优解,也不会导致区间重叠。
这个转移方程实际上就是选择区间 $[l_{a_i},r_{a_i}]$ 里,颜色 $a_i$ 不移动,因为 $f[i]$ 存的是 $i\cdots n$ 里不需要移动的书的最大数量,所以要加上 $r_{a_i}$ 右边的 $f$ ,应该很好理解 ~
**Code**
```cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int N = 5e5 + 7, mod = 1e9 + 7;
typedef long long ll;
typedef int itn;
itn a[N], l[N], r[N];
int cnt[N], cnt_post[N];
itn n, m;
int f[N];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++ i) {
scanf("%d", &a[i]);
if(l[a[i]] == 0) l[a[i]] = i;
r[a[i]] = i;
cnt[a[i]] ++ ;
}
for(int i = n; i >= 1; -- i) {
f[i] = f[i + 1];
cnt_post[a[i]] ++ ;
if(i == l[a[i]])
f[i] = max(f[i], f[r[a[i]] + 1] + cnt[a[i]]);
else f[i] = max(f[i], cnt_post[a[i]]);
}
printf("%d\n", n - f[1]);
return 0;
}
```
当然,我们上面使用逆序来求,实际上正序逆序没有任何区别 ~
-----------
牛逼群友用线段树搞出来了...
wxyyyds
%%%
~~我还没看懂啥意思~~
```cpp
#include <iostream>
namespace wxy{
const int N = 5e5 + 5,inf = 1e9 + 5;
#define int long long
int a[N],f[N],lst[N],fst[N],pre[N],cnt[N],n;
struct node{int l,r,add,max;}t[N << 2];
inline void pushup(int u){t[u].max = std::max(t[u << 1].max,t[u << 1 | 1].max);}
inline void pushdown(int u){
if (t[u].add){
t[u << 1].max += t[u].add; t[u << 1 | 1].max += t[u].add;
t[u << 1].add = t[u << 1 | 1].add = t[u].add; t[u].add = 0;
}
}
inline void build(int u,int l,int r){
t[u].l = l; t[u].r = r; t[u].add = 0;
if (l == r){t[u].max = cnt[l]; return;}
int mid = l + r >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
pushup(u);
}
inline void cge(int u,int l,int r,int v){
if (t[u].l == l && t[u].r == r){
t[u].max += v; t[u].add += v;
return;
}
int mid = t[u].l + t[u].r >> 1;
pushdown(u);
if (r <= mid) cge(u << 1,l,r,v);
else if (l > mid) cge(u << 1 | 1,l,r,v);
else {cge(u << 1,l,mid,v); cge(u << 1 | 1,mid + 1,r,v);}
pushup(u);
}
inline int query(int u,int l,int r){
if (t[u].l == l && t[u].r == r) return t[u].max;
pushdown(u);
int mid = t[u].l + t[u].r >> 1;
if (r <= mid) return query(u << 1,l,r);
else if (l > mid) return query(u << 1 | 1,l,r);
else return std::max(query(u << 1,l,mid),query(u << 1 | 1,mid + 1,r));
}
inline void main(){
std::cin >> n;
for (int i = 1; i <= n; i++) std::cin >> a[i];
for (int i = 1; i <= n; i++){
pre[i] = lst[a[i]];
lst[a[i]] = i;
cnt[a[i]]++;
}
int pos = n;
for (int i = n; i >= 1; i--){
if (a[i] == a[n]) pos = i;
else break;
}
int cr = cnt[a[n]] - (n - pos + 1);
for (int i = 1; i <= n; i++)
if (i != a[n]) cr += cnt[i];
for (int i = 1; i <= n; i++)
if (fst[a[i]] == 0) fst[a[i]] = i;
int premax = 0;
for (int i = 1; i <= n; i++){
if (fst[a[i]] == i){
f[i] = 1;
f[i] = std::max(f[i],premax + 1);
}else{
f[i] = f[pre[i]] + 1;
}
if (lst[a[i]] == i) premax = std::max(premax,f[i]);
}
int ct = 0;
int ans = n - f[n];
for (int i = 1; i <= n; i++){
if (a[i] == a[n]) continue;
if (lst[a[i]] == i) ans = std::min(ans,cr - f[i]);
}
for (int i = 1; i <= n; i++)
if (cnt[i] == 0) cnt[i] = -inf;
build(1,1,n);
for (int i = 1; i <= n; i++){
cge(1,a[i],a[i],-1);
if (lst[a[i]] != i) continue;
if (a[i]-1>=1)cge(1,1,a[i]-1,f[i]);
if (a[i]+1<=n)cge(1,a[i]+1,n,f[i]);
ans = std::min(ans,n - query(1,1,n));
if (a[i]-1>=1)cge(1,1,a[i]-1,-f[i]);
if (a[i]+1<=n)cge(1,a[i]+1,n,-f[i]);
}
std::cout << ans;
}
}signed main(){wxy::main(); return 0;}
```