题目

问题 C: 美感(beautiful)

题目描述

寿寿喜欢有美感的序列。
对于寿寿来说一个序列是有美感的，当且仅当这个序列每两个相邻的数的和是m的倍数。特别的，寿寿认为长度为1的序列也是具有美感的。
寿寿现在随便在纸上写了一个长度为n的序列a，这个序列目前还不具有美感。因此寿寿想通过删除这个序列中的一些数来让它具有美感。
寿寿想知道最少需要删除几个数。

输入

第一行两个整数n和m。
第二行n个正整数表示序列a。

输出

一行一个整数，表示最少需要删除的数字数。

样例输入

1
2

2 2
1 1

样例输出

1

0

提示

样例输入2

1
2

3 2
1 2 1

样例输出2

1

1

样例输入3

1
2

6 3
1 1 4 5 1 4

样例输出3

1

3

【数据范围】
对于10% 的数据，n=2；
对于30% 的数据，n≤20；
对于50% 的数据，m=2；
对于80% 的数据，m≤3；
对于90% 的数据，n,m≤1000；
对于所有数据，1≤n,m≤10^5, 1≤a[i]≤10^9。

题解

emmm,考试的时候估分90分，结果只有10分！！！
啊啊啊，考场代码想不起来了，大家就来看我老师写的吧……

最少删除多少个数字，换个思路就是最多保留多少个数字。
如果a[i]和a[j]保留，且相邻，则(a[i]+a[j])%m=0。这里有个同余知识(A+B)%M=(A%M+B%M)%M (乘法也可以同余)。
对于每个a[i]，如果要保留它，前面的数必须满足a[j]=(m-a[i]%m)%m。用f[i]记录以i余数作为序列最后一个整数的最多保留数量，得到转移有 f[a[i]%m]=f[(m-a[i]%m)%m]+1，最大的f[i]为答案 。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <bits/stdc++.h>
using namespace std;
int n,m,f[1000005],maxn; 
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= n; i++){
		int a;
		scanf("%d",&a);
		f[a%m] = f[(m-a%m)%m]+1;
		maxn = max(maxn,f[a%m]);
	}
	printf("%d",n-maxn);
	return 0;
}