1480 D2. Painting the Array II(贪心)_cf1480d

传送门

题目大意

把数组$a$分成两个不相交的子数组$a^0$和$a^1$

要求$seg(a^0)$和$seg(a^1)$最小

$seg(a)$表示数组$a$中不同的连续段

比如$[1,2,2,2,2,3,3,1]$有四段为$[1,2,3,1]$

---

做法和$D_1$差不多,所以题解也没变多少…

考虑贪心

我们记当前$a^0$最前面的元素为$one$,$a^1$最前面的元素为$two$

那么$a$中的每一个元素,我们依次考虑分配给$a^0$更优还是分配给$a^1$更优

显然把$a$中数字相同的连续段看作一个整体放在数组后更优,所以先缩点

    int temp = 1;
    for(int i=2;i<=n;i++)
    {
    	if( a[i]==a[i-1] )	temp++;
    	else
    	{
    		b[++top] = temp; col[top] = a[i-1];
    		temp = 1;
		}
	}
	b[++top] = temp; col[top] = a[n];
1
2
3
4
5
6
7
8
9
10
11

---

当$one==two$时

显然此时把$col[i]$给哪个子数组都无所谓,随便丢。

当$one!=a[i]\&\&two==col[i]$

把$col[i]$丢在$two$后面答案会加一,更优

把$col[i]$放在$one$后面放弃暂时的收益后续可能更优秀吗??不可能的

末尾什么数字之影响下一次的收益,所以可以让答案不加就不加,不会使答案变劣。

当$two!=a[i]\&\&one==col[i]$

同上,把$col[i]$丢在$one$后面更好

当$one!=two\&\&one!=col[i]\&\&two!=col[i]$

此时放在哪个位置都会让答案加一,那么怎么选择??

定义$nxt[i]$为数字$i$出现最近的位置

如果$nxt[one]<nxt[two]$,放在$two$后面更优,有更多机会合并$one$

如果$nxt[one]>nxt[two]$,放在$one$后面更优,有更多机会合并$two$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int n,a[maxn],vis[maxn],b[maxn],top,col[maxn],id[maxn];
vector<int>vec[maxn];
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)	cin >> a[i];
    int temp = 1;
    for(int i=2;i<=n;i++)
    {
    	if( a[i]==a[i-1] )	temp++;
    	else
    	{
    		b[++top] = temp; col[top] = a[i-1];
    		temp = 1;
		}
	}
	b[++top] = temp; col[top] = a[n];
	for(int i=1;i<=top;i++)
		vec[col[i]].push_back(i);
	int ans = 0,one = -1,two = -1;
	for(int i=1;i<=top;i++)
	{
		id[col[i]]++;
		if( one==two )
		{
			if( one!=col[i] )	one = col[i],ans++;
		}
		else if( one!=col[i]&&two==col[i] )	two = col[i];
		else if( two!=col[i]&&one==col[i] )	one = col[i];
		else
		{
			if( one==-1 )	one = col[i],ans++;
			else if( two==-1 )	two = col[i],ans++;
			else
			{
				int nxt_one = n+1, nxt_two = n+1;
				if( id[one]<vec[one].size() )	nxt_one = vec[one][id[one]];
				if( id[two]<vec[two].size() )	nxt_two = vec[two][id[two]];
				if( nxt_one<nxt_two )	two = col[i],ans++;
				else	one = col[i],ans++;
			}
		}
	}
	cout << ans;
}
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