题解：洛谷 P10878 [JRKSJ R9] 在相思树下 III

原题链接

解析

在操作一时，最小值如果在最后一位，其无法更新任何数，会被删除；否则不在最后一位时一定会被其右侧更大的数更新。所以在操作一时，最小值一定会被更新掉。

同理，在操作二时，最大值一定会被更新掉。

由此，操作一决定了答案的下限，操作二决定了答案的上限。

所以可以得出贪心策略：先进行 \(m\) 次操作一，后进行 \(n-m-1\) 次操作二。

进行完操作一以后，很明显如果只进行操作二，那么最后剩下的一定是剩下数的最小值。

\(m\) 次操作一的时间复杂度为 \(O(NM)\)，可以得 \(40\) 分，但操作一的过程还可以优化。

因为 \(m\) 次操作一可以使 \(a_i\) 影响到 \(a_{i-1},a_{i-2},\cdots,a_{i-m}\)，所以反过来，\(a_i\) 在经过 \(m\) 次操作一以后被 \(a_{i+1},a_{i+2},\cdots,a_{i+m}\) 影响，\(a_i\) 即为 \(\max\{a_j\}\)，其中 \(j \in [i+1,i+m]\)。

问题转化成了“对于每个数，求它右边 \(m\) 个数的最大值”，可以用优先队列维护。

代码：

40 Pts 代码

#include<cstdio>
#include<algorithm>
using namespace std;

const int N=1e6+5;
int n,m,a[N];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n-i;j++)
			a[j]=max(a[j],a[j+1]);
	}
	int ans=0x3f3f3f3f;
	for(int i=1;i<=n-m;i++)
		ans=min(ans,a[i]);
	printf("%d\n",ans);
	return 0;
}

100Pts 代码

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

const int N=1e6+5;
int n,m,a[N],b[N];
deque<int> q;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
		if(!q.empty() && i-q.front()>m) q.pop_front();
		while(!q.empty() && a[q.back()]<a[i]) q.pop_back();
		q.push_back(i);
		if(i>=m+1) b[i-m]=a[q.front()];
	}
	int ans=0x3f3f3f3f;
	for(int i=1;i<=n-m;i++)
		ans=min(ans,b[i]);
	printf("%d\n",ans);
	return 0;
}