招商银行笔试三题 暨和99°兄的日常联谊

缘起

和 99° 兄（猜测不是妹子~）的日常联谊。

秋高气爽，招商银行开始面试~ 如下三题 (可惜，都无处提交~ 在我看来, 不能提交ac的算法都是 耍流氓！！！)

分析

第一题

1
2
给定一个长度为n的整数数列A，要求修改其中尽可能少的数，使得整个数列变成一个不下降数列，即
A1 ≤ A2 ≤ A3 ≤ … ≤ An。

第二题

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
小招喵要完成n个任务，它制定了-一个计划，计划第i天完成第i个任务，每个任务可能有前置任务，在完成第i个任
务时，必须先完成它的前置任务才行。问小招喵要想实现它的计划，每天至少要完成多少个任务?输入:

一个整数n,表示要完成的任务数，2=<n<=10000。 接下来n行，每行第一个数字k表示该任务的前置任务数，剩下的
k个数字分别表示前置任务编号。输出:

n个数字，每个数字以一个空格间隔，表示每天至少完成的任务数

样例输入:
3
1 2 
0
2 1 2

样例输出:
2 0 1

说明:任务1有1个前置任务2,第1天要想完成任务1,需先完成任务2，所以第1天至少完成2个任务。第2天计划完成任
务2，因为任务2已在第一天完成，且任务2无前置任务，所以第2天至少完成0个任务。第3天计划完成任务3,任务3有
两个前置任务1、2，在前两天都已完成，所以这-天只需完成任务3，至少完成1个任务即可。样例输入:

5
4 2 3 4 5
1 1
2 1 2
0
1 3

样例输出:
5 0 0 0 0

说明:第1个任务有4个前置任务2、3、4、5,要想完成1，需先完成2、3、4、5，那么第1天至少完成5个任务。接下
来的第2、3、4、5天每天完成0个任务，因为在第1天已完成全部5个任务。

第三题

1
2
3
4
5
6
7
8
9
10
11
12
13
题目描述
小招喵给出一个包含几个整数的数组
每一次操作小招喵可以选择数组中若干个下标不同的元素，对选中的每一个元素，都执行下列改变:假设选中的元素
为x那么就将x替换为(x+ 1) mod m,即选中每个元素自增1， 如果变为m则归零。请问最少执行多少次操作，小招
喵可以把这个数组变为个数组元素非递减的数组。

输入描述:
第一行是n,m两个整数, 然后是n个整数 a1,...,an
满足
1<=n,m<=30万, 0<=ai<m

输出描述:
最少操作次数。

第一题简单~ 不想写代码了. 就是求出LIS. 然后将不在此LIS上的元素修改成为它之前的LIS中的元素即可. 即

修改为（注意红色的水平线即可）

第二题也简单（一开始瞄一眼的时候还以为要拓扑排序, 后来一想连拓扑排序都不需要）. 反向建图然后开一个哈希数组即可.

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
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#define LOCAL

const int maxn = 10005;
int n, a[maxn], head[maxn];
bool v[maxn];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	memset(head, -1, sizeof(head));
	scanf("%d", &n);
	for (int i = 1,k,sum;i<=n;i++)
	{
		scanf("%d", &k);
		sum = 0;
		while(k--)
		{
			int x;
			scanf("%d", &x);
			if (!v[x])
			{
				v[x] = true;
				sum++;
			}
		}
		if (!v[i])
		{
			sum++;
			v[i] = true;
		}
		printf("%d ", sum);
	}
	return 0;
}

第三题稍微有点意思. 我原先做过一道”最小代价将序列变单调”的题目（【2】）. 本题其实差不多思路. 

1
2
3
4
5
令
dp[i][j]=a[0,..,i]修改为以j为末尾元素的最小操作次数. 则
dp[i][j]=min_{0<=k<=j}{max(dp[i-1][k], moves[i][j])}
		=max{min_{0<=k<=j}dp[i-1][k], moves[i][j]} (这个等式很好证明, 只需要讨论一下t=min_{0<=k<=j}dp[i-1][k]和moves[i][j]之间的大小关系即可)
其中 moves[i][j]是a[i]变动到j的操作次数.

注意, 不可以令dp[i][j]=a[0,…,n-1]中某个数作为结尾的最小操作数（即不能像【2】中那样操作）, 因为中间的状态j（0<j<m）都是要用的， 例如 7 和 5 变动到以5结尾的单调非降子序列（m=8）的话, 则只需要1次变动即可, 即

7->0, 所以0虽然不是5和7中任何一个, 但是dp的时候, 也是可能转移到0的. 所以必须将0~m-1这m个状态都考虑进去.

即我们得到了

1
2
3
4
5
6
7
8
9
dp[i][j]=max{min_{0<=k<=j}dp[i-1][k], moves[i][j]}
1<=i<n, 0<=j<m
而dp[0][0,...,m-1]很好预处理得到的. 使用滚动数组优化上面的dp方程为
for(int i = 1; i<n; i++)
{
	dp[j] = max{moves[i][j], min{dp[0],...,dp[j]}}
}
其中min{dp[0],...,dp[j]} 不需要担心, O(1)时间就可以维护了.
最后min{dp[0],...,dp[m-1]}就是答案

遂写下如下代码（可惜无处提交）

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
#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
#define LOCAL
#define ABS(x,y) ((x)>(y)?((x)-(y)):((y)-(x)))
const int maxn = 300005;

int n,m, a[maxn], dp[maxn];

inline int moves(int i, int j) // a[i]按规则变动到j需要移动的步数
{
	int ans = j-a[i];
	if (a[i]>j)
	{
		ans+=m;
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &m);
	for (int i = 0; i<n; i++)
	{
		scanf("%d", a+i);
	}
	for (int i = 0; i<m; i++)
	{
		dp[i] = moves(0, i);
	} // dp初始化
	for (int i = 1,t; i<n; i++) // 开始dp
	{
		t = dp[0];
		for (int j = 0; j<m; j++)
		{
			t = min(t, dp[j]);
			dp[j] = max(t, moves(i, j));
		}
	}
	int ans = 0x3f3f3f3f;
	for (int i = 0; i<m; i++)
	{
		ans = min(ans, dp[i]);
	}
	printf("%d\n", ans);
	return 0;
}

自己yy了几组测试数据

1
2
3
4
5
6
7
8
9
10
11
6 8
7 5 6 3 2 1
答案是3

3 2
1 0 1
答案是1

3 2
1 0 0
答案也是1

唯一遗憾的是, 算法是 O(N*M)的. 会T啊~ 各位菊苣有没有什么优化的点子? 请留言，谢谢！

参考

【1】https://yfsyfs.github.io/2019/08/19/poj-2533-Longest-Ordered-Subsequence-LIS-dp-%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97/

【2】https://yfsyfs.github.io/2019/08/28/POJ-3666-Making-the-Grade-dp/