Codeforces Round 915 (Div. 2) D题 单调栈，特殊情况入手

Problem - D - Codeforces

目录

题意：

思路：

把0放后面：

————

然后看懂下面思路，理解单调栈：

细节：

核心代码：

---

?

题意：

mex指的是该数组缺的最小的自然数，例如：数组0 1 2 缺3 ，0 1 3 缺2， 1 2 3 4 5缺0。

对set数组0 1 2来说，有0 ， 0 1 ，0 1 2 ，而0缺1,? ?0 1缺2，? ?0 1 2缺3 ，所以cost加起来就是1+2+3=6。

然后给的数组大小为n，里面的数分别是0 ~ n - 1?

这个数组可以进行若干次循环移位，即第一位移到最后一位。

问最大cost

思路：

把0放后面：

“特殊情况入手”，指的是0在最后一位时。

当0在最后一位时，前面所有数的cost都是0，因为它们缺0 。而0之前缺的是n，所以cost是n。

参考方式：（arr就是题目给的数组，我用的vector）

int zerop;
for (int i = 0; i < n; i++)
{
	if (arr[i] == 0)
	{
		zerop = i;
		break;
	}
}
vector<int>tmp(arr.begin() + zerop+1, arr.end());
for (int j = 0; j <= zerop; j++)
{
	tmp.push_back(arr[j]);
}

————

然后看懂下面思路，理解单调栈：

1.对于1 4 5 2 3 0，同我们刚开始的讲解，0前面cost全是0，而0自己是n即这里的6。这个时候我们进行操作入栈0。

至此，这种情况的cost就算完了。然后循环移位。

接下俩情况分两类：

①.（情况2 3 4 6）

如果移位后最后一位的是一个比栈内数都大数，那么前面的比他小的数都有的，此时他的cost就是n（末尾是整个数组，n-1前所有的数都有）。而0前失去了这个数，那么0的cost就是这个数(代指a）。

那下一次移位最后一位b还是最大呢，同理，0前缺的最大的自然数还是上一个数a，而上一个数a也只缺这个新数b，cost即为b。b则取代最后的位置，cost为n。

②.（情况5）

你一旦把小的数c放后面，0后的c前面的那些比它大的数都“失了效”，它们之前缺的最大的自然数变成了这个数c，所以从栈内删掉这些数，把他们的cost改为c即可。

接下来遇到的情况也只会是这两种。每次算出cost，记录最大的即可。

细节：

为了方便算cost，一般就把数都放栈时，顺便求和了。

相同的数放单调栈后面会超时，所以可以另起一个栈记录数目（一起入栈一起出栈即可），这样相同的数入栈出栈非常快。

（所以单调栈就是栈里面的数是单调的嘛，这道题有点脑筋急转弯了，苛刻的条件，只能多刷题啦）

核心代码：

void solve()
{
	int n;
	cin >> n;
	vector<int>arr(n);
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	ll ans = 0;
	int zerop;
	for (int i = 0; i < n; i++)
	{
		if (arr[i] == 0)
		{
			zerop = i;
			break;
		}
	}
	vector<int>tmp(arr.begin() + zerop+1, arr.end());
	for (int j = 0; j <= zerop; j++)
	{
		tmp.push_back(arr[j]);
	}
	//tmp结尾为0的cyclic
	stack<ll>monotone,numst;
	monotone.push(0); numst.push(1);
	ll sum = 0;
	sum += tmp.size();//总数组的
	ans = max(sum, ans);
	//你一旦把小的数放后面，前面那些大的数都失了效
	
	//如果你放的是一个“最大的数”，那么前面的小的数都有的，你替代0的位置，但对0来说，失去了你
	//那再放一个大的数呢，0已失去小的，而那个小的也只缺你，你则取代最后的位置。
	for (int i = 0; i < n-1; i++)
	{
		if (tmp[i] > monotone.top())
		{
			monotone.push(tmp[i]); numst.push(1);
			sum += tmp[i];
		}
		else
		{
			//把相同的数组装起来了
			ll count = 1;
			while (tmp[i] < monotone.top())
			{
				sum -= monotone.top()*numst.top(); 
				count+=numst.top();
				monotone.pop(); numst.pop();
			}

			monotone.push(tmp[i]); numst.push(count);
			sum += tmp[i]*count;
		}
		ans = max(ans, sum);
	}

	cout << ans << endl;
}