STL-CodeChef Cutting Plants题解

单调队列哦

我要造福后人，因为题解太jb难找了

题意：

2个操作
找一段l-r区间，取其<=最小值的任意高度 ,记为h
将l-r变为h
时间复杂度暂时归为n吧

思路：(思路应该很容易跟上)

最特殊的：L=R，来嘛我每个独自减
那为什么会有-1呢
涨不回去呗（bi>ai）

现在关键在于我可不可以（一起减）
想一下方案数减少的条件
eg:

5 7
2 3
我可以5-7那里一起修减到3，在把5修建到2
还是要用两次

所以当且仅当出现连续的bi时，可以减少方案书
上了个厕所（肾虚呢......在whz和ljh眼下悄悄c了两把）
一定要连续吗？
例如2222222212(目标）
我还是可以一下剪掉
但是2222222232，就不能，要分3次了

上面那种情况再拓展下
3333333332133
那就是找上面那种情况 ，用n减去多余步数就是答案
多余步数就是 重复的个数-1 （如上面，ans=13-10=3)
那要是多重呢
5555555 333333 222222 111111 22222222 333333333 555555
是不是就相当于5321235 ?ans=7-1-1-1=4;
那上面那个，是不是相当于3213?
woc,我好巨

现在我们就已经找到这道题很多性质了
验证一下：2121212，ans=7-3=4?对的！
那贪心肯定没问题，好难写，复杂度也可能有问题
思路理清了，想想这个该用什么数据结构来搞
管他呢，乱搞！

啊啊啊，错了
看题解
没找到
老师找到了，同他的话来说："抽象"
但其实有了以上的认识，也很明了了
https://blog.csdn.net/noone0/article/details/82049287
单调队列：
所以说还要满足减去的<=min(a[i])-->不然的话我不要a数组就做出来了
这个就是问题所在了
然后就单调队列找这段区间

做法：

建立bi严格递减的单调队列 ,因为你要砍的话，肯定是砍一个b[i]
同时要求这段区间内最大也要是a[i]，这是为了保证对于原数组（“砍得到”），从而避免答案偏大
如果出现了队列清空的情况（eg.343）
就说明有了3 4这一下了
又如果出现了b[i] =bi-1
就说明有3 3这一下了
3 3就可以直接缩减为3（上面找过这个规律的），同样也是避免答案偏大

为什么这么做
假设现在有一个单调递减的b数组，a数组都是极大的
那肯定就是要减少b.size()次
有一个不递增的b数组
那答案就是去重后的b.size()次
那遇到343这样的怎么办？
单调队列会在第一个3加一次，3处加一次，由于单调递减，在第二个3中就相当于
将第一个和第二个3合并了，没有计算答案，因此答案为2
最后吧a[i]的限制加上就行了吧

代码：

#include<bits/stdc++.h>
using namespace std;

int a[200005];
int b[200005];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int main(){
//    ios::sync_with_stdio(false);
	int t;
	t=read();
	while(t--){
		int n;
		n=read();
		bool haveans=1;
		for(int i=1;i<=n;i++){
			a[i]=read();
		}
		for(int i=1;i<=n;i++){
			b[i]=read();
			if(b[i]>a[i]){
				haveans=0;
//				break;----------!!!!!!!!!!!!!!我也不知道为什么写了个这个，我是傻逼，70分wa这 
			}
		}
		if(!haveans){
			puts("-1");
			continue;
		}
		deque<int>q;//已经自动清空了 
		int res=0;
		for(int i=1;i<=n;i++){//DEQUE内存的是能一直运行到现在的h 
			while(!q.empty()&&b[i]>q.back()){
				q.pop_back();
			}	
			while(!q.empty()&&a[i]<q.front()){
				q.pop_front();
			}
			if(a[i]!=b[i]&&(q.empty()||b[i]!=q.back())){//找到了可以操作的
			/*
			这里给一个解释
			a[i]!=b[i]是为了这一次操作行之有效
			q.empty（不得不从新分离一次了）||b[i]!=q.back()(会多减一次） 
			*/
				res++;
				q.push_back(b[i]);
			}
		}
		cout<<res<<endl;
	} 
}