乱搞为什么AC了
查看原帖
乱搞为什么AC了
1282142
Konjac_C楼主2024/8/15 19:29

我的思路是求 m 次操作一后的数列中,最小的数是答案。

我转化成了求1~m,2~m+1,3~m+2...中的最大值的最小值。但是在Subtask1中WA了几个点,后面特判过了,要怎那么做才不用特判

void mx()
{
	h=1,t=0;
	for(int i=1;i<=n;i++){
		while(h<=t && a[q[t]]<=a[i]) t--;
		q[++t]=i;
		if(q[h]<i-k+1) h++;
		if(i>=k) ans=min(ans,a[q[h]]);
	}
}
main()
{
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(n<=5000){
		for(int i=1;i<=k;i++){
			for(int i=1;i<=n;i++) b[i]=a[i];
			for(int i=1;i<n;i++) a[i]=max(b[i],b[i+1]);
			n--;
		}
		sort(a+1,a+1+n);
		cout<<a[1];
		return 0;
	} 
	mx();
	cout<<ans;
	return 0;
}
2024/8/15 19:29
加载中...