1. 题目

题目链接:P2418「yyy loves OI IV」

题目背景

某校 2015届有两位 OI 神牛,yyy 和 c01。

题目描述

全校除他们以外的 NN 名学生,每人都会膜拜他们中的某一个人。现在老师要给他们分宿舍了。但是,问题来了:

同一间宿舍里的人要么膜拜同一位大牛,要么膜拜 yyy 和 c01 的人数的差的绝对值不超过 MM。否则他们就会打起来。

为了方便,老师让 NN 名学生站成一排,只有连续地站在一起的人才能分进同一个宿舍。

假设每间宿舍能容纳任意多的人,请问最少要安排几个宿舍?

输入格式

第一行,两个正整数 NNMM

2N+12 \cdots N+1 行,每行一个整数 1122,第 ii 行的数字表示从左往右数第 i1i-1 个人膜拜的大牛。

11 表示 yyy,22 表示c01。

输出格式

一行,一个整数,表示最少要安排几个宿舍。

输入输出样例

输入 #1

1
2
3
4
5
6
5 1
1
1
2
2
1

输出 #1

1
1

说明/提示

难度题,做好心理准备~

测试点编号 N的范围 M的范围
1~3 2,500\leq 2,500 10\leq 10
4~5 500,000\leq 500,000 10\leq 10
6~10 500,000\leq 500,000 2,000\leq 2,000

2. 题解

分析

从第一个同学开始,逐步往最后一个同学扫描;易知除了最后一个宿舍,其余宿舍:

  • 要么全部膜拜同一个大佬
  • 要么二者数量之差的绝对值等于 MM

dp[i]dp[i] 表示处理完前 ii 个同学至少需要的宿舍数量,stu[i]stu[i] 表示第 ii 个同学的膜拜的大佬(1-1 代表 1111 代表 22),sum[i]=stu[i]sum[i] = \sum stu[i] 表示前 ii 个同学膜拜的大佬的代数数量和(即膜拜两位大佬的数量之差,这便是将 1122 映射为 1-111 的原因:方便处理),ump[u]ump[u] 表示对于当前输入,膜拜者二者数量相差绝对值为 uu 时所需的最少宿舍数量(由于 uu 的取值范围较大,故选择 unordered_map 来实现存储记录)。

【注】可以设定 ump[u]ump[u] 的原因在于,最优情况下,所有宿舍出现的情况是一样的,即膜拜数量最多的是同一位大佬(不然由于宿舍数量没有上限,则可以合并相邻膜拜者数量较大的一者不同的宿舍,仍然满足题意条件)。

  • 对于第一种情况:可以通过设定记录上一个不同记录值的位置来实现;即 dp[i]dp[last]+1dp[i] \leq dp[last] + 1,其中 lastlast 为与同学 ii 膜拜的大佬相对的上一个同学的位置。即处理到当前同学,最多比上一个信仰不同的同学的宿舍数量多 11(因为此时两者之间的同学膜拜的都是同一个大佬)。

  • 对于第二种情况:dp[i]ump[abs(sum[i])M]+1dp[i] \leq ump[abs(sum[i]) - M] + 1,即至少小于等于比现在少 MM 个数量差的情况下所需最少宿舍数量 +1+1

因此,对于 u0u \leq 0 而言,ump[u]=0ump[u] = 0。因为 abs(sum[i])M0abs(sum[i]) - M \leq 0 说明此时膜拜二者的数量差还没有超过 MM ,因此此时最多需要 11 个宿舍,即 ump[abs(sum[i])M]=0ump[abs(sum[i]) - M] = 0

综合二者,则可以列出状态转移方程:dp[i]=min(dp[last]+1,ump[abs(sum[i])M]+1)dp[i] = min(dp[last]+1, ump[abs(sum[i]) - M] + 1)。最终结果即为 dp[n]dp[n]

代码

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 5;

int stu[MAXN], sum[MAXN], dp[MAXN];

//终极快读
char buf[1<<22],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)

//快读
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}

void input(int n) {
for(int i = 1; i <= n; ++i) {
int a = read();
stu[i] = 2*a - 3;
}
}

int myabs(int x) {
return x < 0 ? -x : x;
}

void init(int n) {
for(int i = 1; i <= n; ++i) {
sum[i] = sum[i-1] + stu[i];
}
}

unordered_map <int,int> ump;
void update(int u, int x) {
if(u > 0) {
if(ump.count(u) == 0) {
ump[u] = x;
} else {
ump[u] = min(ump[u], x);
}
}
}

int query(int u) {
if(ump.count(u) == 0) {
if(u <= 0) {
return 0;
} else {
return MAXN;
}
}
return ump[u];
}

int answer(int n, int m) {
int last1 = 0, last2 = 0;
for(int i = 1; i <= n; ++i) {
if(stu[i] == 1) {
dp[i] = dp[last2] + 1;
last1 = i;
} else {
dp[i] = dp[last1] + 1;
last2 = i;
}
dp[i] = min(dp[i], query(myabs(sum[i])-m)+1);
update(myabs(sum[i]), dp[i]);
}
return dp[n];
}

int main()
{
int n, m;
scanf("%d%d", &n, &m);
input(n);
init(n);
printf("%d\n", answer(n,m));
return 0;
}