ACWING 651. 逛画展

原题链接：https://www.acwing.com/problem/content/description/653/

博览馆正在展出由世上最佳的 M 位画家所画的图画,你想到博览馆去看这些才华横溢的大师们的作品。
可是，那里的博览馆有一个很奇怪的规定，就是在购买门票时必须说明两个数字，
l和r，代表他要看展览中的第 l 幅至第 r 幅画(包含 l 和 r)之间的所有图画，而门票的价钱就是一张图画一元。
为了看到更多名师的画，你希望入场后可以看到所有名师的图画(至少各一张)。
但是你想要花费最少,现在你需要编写计算机程序,来求出最小花费的的 l 值和 r 值。

输入输出格式

输入格式：

第一行是 N 和 M，分别代表博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。
其后的一行包含 N 个数字，它们都介于 1 和 M 之间，代表该位名师的编号。

输出格式：

l和r(l<=r),中间有一个空格,并且题目保证有解,如果多解,输出l最小的. 输入输出样例 输入样例#1：

12 5
2 5 3 1 3 2 4 1 1 5 4 3

输出样例#1：

2 7

答案参考自秦淮岸灯火阑珊的2019年4月11日单调队列讲义

秦淮岸灯火阑珊看来是搞ACM竞赛的。搞ACM的人软件工程能力都不怎么样，代码可读性极差，可维护性极差，可复用性极差。ACM的题，输入还要有输入格式，一行一行来的。ACM没有方法这个概念，难怪ACM题目答案都是单体式代码！我如果当时搞ACM了，如今管理不了几百万行的解决方案。

这道题根本不需要特殊的“单调队列”结构，用一个链表即可完成，不过秦淮岸灯火阑珊的思路还是很巧妙的。

可读性半优化后的C#代码如下。

/// <summary>
/// 
/// </summary>
/// <param name="m">作者种类</param>
/// <param name="works">名画列表</param>
/// <returns>[l,r]</returns>
public int[] GetTicketRange(int m, int[] works)
{
	var queue = new LinkedList<int>();
	int n = works.Length;
	int[] workCount = new int[m];
	int collectedWorks = 0;
	int ans = int.MaxValue;
	int l = 0, r = 0;
	for (int i = 0; i < n; i++)
	{
		if (workCount[works[i] - 1] == 0) //a[i]这幅名画的作者没有出现过。
			collectedWorks++;
		//这里特殊注意:因为如果说我们当前区间已经满足题意条件,那么我们后面所有的区间统统都会满足条件,因为我们的出队操作,保证我们必须是名画种类递增.

		queue.AddLast(i);

		workCount[works[i] - 1]++;

		while (workCount[works[queue.First.Value] - 1] >= 2)//队头名画所代表的画家的画在队列中至少有两幅.
		{
			workCount[works[queue.First.Value] - 1]--;//队头不要了
			queue.RemoveFirst();
		}

		if (collectedWorks >= m && queue.Last.Value - queue.First.Value + 1 < ans)//如果集齐各大名画,同时候选答案区间花费的费用更小.
		{
			l = queue.First.Value;//l
			r = queue.Last.Value;//r
			ans = queue.Last.Value - queue.First.Value + 1;//费用
		}
	}
	return new int[] { l + 1, r + 1 };
}

• 秦淮岸灯火阑珊. 2019年4月11日单调队列讲义. . 2019-04-11 [2019-09-11].
• . 651. 逛画展. acwing. [2019-09-11].