8月18日测试总结
触手（ xyx ）
题目大意：
给定 \(n\) 个柱子，每一次只能刷相邻的 \(x\) 个柱子，在这 \(x\) 个柱子中，只能刷到其中高度最低的，问最大的粉刷面积及其最少操作次数
思路：
首先，用一个单调队列维护可能的操作高度，然后，再用一个单调队列维护当前位置的最终高度，也就是所有操作高度中最高的那一个。最后，对于一个还未达到最终高度的柱子找到最长的合法操作即可
Code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+1;
int ans;
int n,x,tot;
int h[maxn];
int b[maxn];//对它的操作高度（不一定是最终高度）
int c[maxn];//记录最终高度
int qmin[maxn];
int qmax[maxn];
int head=1,tail;
signed main()
{
//freopen("xyx4.in","r",stdin);
std::ios::sync_with_stdio(false);
cin>>n>>x;
for(int i=1;i<=n;++i)cin>>h[i];
for(int i=1;i<=n;++i)//单调递增队列（以i为队首，长度为x的一串中高度最小的）
{
while(head<=tail&&i-qmin[head]+1>x)++head;
while(head<=tail&&h[qmin[tail]]>=h[i])--tail;
qmin[++tail]=i;
if(i>=x)
b[i-x+1]=h[qmin[head]];
}
head=1,tail=0;
for(int i=1;i<=n;++i)//单调递减队列（找最终高度）
{
while(head<=tail&&i-qmax[head]+1>x)++head;
while(head<=tail&&b[qmax[tail]]<=b[i])--tail;
qmax[++tail]=i;
c[i]=b[qmax[head]];
ans+=c[i];
}
for(int i=1;i<=n;++i)
{
int j=i;
while(j<n&&c[j+1]==c[i])++j;//找到包括第i位的最长的合法操作
tot+=(j-i+1+x-1)/x;
i=j;
}
cout<<ans<<endl;
cout<<tot<<endl;
return 0;
}
/*
5 2
1 2 4 2 3
9
3
1 2 2 2 0
1 2 2 2 2
8 2
2 4 4 6 5 2 4 1
25
5
2 4 4 5 2 2 1 0
2 4 4 5 5 2 2 1
*/