我开始写的时候楼下就开始咬打火机，等我发出来了他还在咬…… 此题解正在编辑中，有需要请先查看其他人的(没有其他人就去咬打火机) ————lxm59_

首先求牙刷刷的面积，应该让油漆筒刷的越多越好，油漆筒最高高度是这一区间里高度的最小值，所以用单调队列(不用你就T了)求每一个栅栏最高刷到哪里，用高度减去刷的高度再求和，就是第一问。 然后观察规律，发现当刷的最高高度发生变化时，就必须是另一刷子才能刷到的。而且当上一刷子刷到的区域覆盖不到时，也要补一刷子。 配合代码更清晰：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, X, h[1000005], q[1000005], head, tail, b[1000005], t[1000005], highnow, border, ans, cnt;
int main()
{
    // 输入
	scanf("%lld%lld", &N, &X);
	for (int i = 1; i <= N; i++)
		scanf("%lld", &h[i]);
    // 第一部分===================================================
    // 第一次单调队列，对于每个区间，求区间内的最小值
	head = 1, tail = 0;
	for (int i = 1; i <= N; i++)
	{
		while (head <= tail && q[head] <= i - X) head++; // 超范围的出去
		while (head <= tail && h[q[tail]] > h[i]) tail--; // 不够小的出去
		tail++;
		q[tail] = i; // 新的放进来
		if (i - X + 1 >= 0) b[i - X + 1] = h[q[head]];
	}
    // 第二次单调队列，对于每块木板，求能刷到他的区间最高高度的最大值
	head = 1, tail = 0;
	for (int i = 1; i <= N; i++)
	{
		while (head <= tail && q[head] <= i - X) head++;
		while (head <= tail && b[q[tail]] < b[i]) tail--; // 这里是不够大的出去
		tail++;
		q[tail] = i;
		t[i] = b[q[head]];
	}
    // 最后遍历所有木板，求出没刷的面积
	for (int i = 1; i <= N; i++)
		ans += h[i] - t[i];
    // 第二部分===================================================
    // highnow是上一刷子的高度，border是上一刷子最大刷到的范围
	for (int i = 1; i <= N; i++)
	{
		if (t[i] != highnow || border < i) // 当增高或者超出范围
		{
			highnow = t[i]; // 刷新高度
			border = i + X - 1; // 刷新范围
			cnt++; // 加一刷子
		}
	}
	printf("%lld\n%lld\n", ans, cnt); // 美滋滋的输出
	return 0;
}

纯净版(用于AC)：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, X, h[1000005], q[1000005], head, tail, b[1000005], t[1000005], highnow, border, ans, cnt;
int main()
{
	scanf("%lld%lld", &N, &X);
	for (int i = 1; i <= N; i++)
		scanf("%lld", &h[i]);
	head = 1, tail = 0;
	for (int i = 1; i <= N; i++)
	{
		while (head <= tail && q[head] <= i - X) head++;
		while (head <= tail && h[q[tail]] > h[i]) tail--;
		tail++;
		q[tail] = i;
		if (i - X + 1 >= 0) b[i - X + 1] = h[q[head]];
	}
	head = 1, tail = 0;
	for (int i = 1; i <= N; i++)
	{
		while (head <= tail && q[head] <= i - X) head++;
		while (head <= tail && b[q[tail]] < b[i]) tail--;
		tail++;
		q[tail] = i;
		t[i] = b[q[head]];
	}
	for (int i = 1; i <= N; i++)
		ans += h[i] - t[i];
	for (int i = 1; i <= N; i++)
	{
		if (t[i] != highnow || border < i)
		{
			highnow = t[i];
			border = i + X - 1;
			cnt++;
		}
	}
	printf("%lld\n%lld\n", ans, cnt);
	return 0;
}

这题真是道难题，两个步骤全需要独立求解，并且你也需要时时刻刻保证时间复杂度不是O( n² )

也就是说你爆搜一定会超时并且你第二个问题还没有一定的贪心策略

爆搜第一个问题的策略就是模拟一个数在x(题中有解释)个长度的连续序列中的所有情况取这个数列最小值，再把所有情况的最小值取最大值，显然O( n² )不咋靠谱，所以我们需要优化

第一个想到的是双指针和滑动窗口，然后想起来前几天的优先队列，还有单调队列

最后觉得单调队列最靠谱

单调队列基础伪代码

for( int i = 1 ; i <= n ; i ++ )
{
    while( head <= tail and 需要的操作 ) head ++ ;
    while( head <= tail and 需要的操作 ) tail -- ;
    tail  ++ ;
    q[ tail ] = 你需要的数字 ;
    你需要的处理 ;
}

然后这题你会发现一次单调队列还是会超时，所以需要两次(讲不明白，自己按伪代码试试)

本题核心：单调队列

第一次处理:brush数组,存储h[ i ]到h[ i + x - 1 ] 可以涂多高的油漆
第二次处理:brush2数组,存储h[ i ]可以涂最高多高的油漆
两个数组都比较有用

int head = 1 , tail = 0 ;
for( int i = 1 ; i <= n ; i ++ )
{
    while( head <= tail and i - q[ head ] + 1 > x ) head ++ ;
    while( head <= tail and h[ i ] <= h[ q[ tail ] ] ) tail -- ;
    tail  ++ ;
    q[ tail ] = i ;
    if( i - x + 1 >= 0 ) brush[ i - x + 1 ] = h[ q[ head ] ] ;
}
head = 1 , tail = 0 ;
for( int i = 1 ; i <= n ; i ++ )
{
    while( head <= tail and i - q[ head ] + 1 >= x ) head ++ ;
    while( head <= tail and brush[ i ] >= brush[ q[ tail ] ] ) tail -- ;
    tail  ++ ;
    q[ tail ] = i ;
    brush2[ i ] = brush[ q[ head ] ] ;
}

处理完后的brush2数组就是我们需要的每个木板最高可以涂多高的油漆

本题核心2:贪心策略制定

可以思考一下
设上一个涂的地方为p,涂的高度为h1
那么是不是如果i(循环变量)在 p ~ p + x - 1 以内时如果brush2[ i ] != h1 的情况下
是不是就应该再涂一遍
如果i超过 p + x - 1 是不是也应该另起再涂一遍
并且要保证最小只有这两种情况可以再涂一遍

所以写出代码

int p = 0 , h1 = 0 ;
for( int i = 1 ; i <= n ; i ++ )
{
    if( i >= p and i <= p + x - 1 and h1 != brush2[ i ] )
    {
        ans ++ ;
        h1 = brush2[ i ] ;
        p = i ;
    }
    if( i > p + x - 1 )
    {
        ans ++ ;
        h1 = brush2[ i ] ;
        p = i ;
    }
    ans2 += h[ i ] ;//ans2代表需要涂的面积总数
    ans3 += brush2[ i ] ;//ans3代表最多拿滚筒涂的面积总数
    //最后ans2 - ans3 即为最少用粉笔涂的面积总数
}

这样两个步骤就都完成了

代码见下

#include<bits/stdc++.h>
using namespace std;
int n , x ;
int h[ 1000001 ] , brush[ 1000001 ] , brush2[ 1000001 ] ;
int q[ 1000001 ] ;
long long ans , ans2 , ans3 ;
int main()
{
    ios::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cin >> n >> x ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        cin >> h[ i ] ;
    }
    int head = 1 , tail = 0 ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        while( head <= tail and i - q[ head ] + 1 > x ) head ++ ;
        while( head <= tail and h[ i ] <= h[ q[ tail ] ] ) tail -- ;
        tail  ++ ;
        q[ tail ] = i ;
        if( i - x + 1 >= 0 ) brush[ i - x + 1 ] = h[ q[ head ] ] ;
    }
    head = 1 , tail = 0 ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        while( head <= tail and i - q[ head ] + 1 > x ) head ++ ;
        while( head <= tail and brush[ i ] >= brush[ q[ tail ] ] ) tail -- ;
        tail  ++ ;
        q[ tail ] = i ;
        brush2[ i ] = brush[ q[ head ] ] ;
    }
    int p = 0 , h1 = 0 ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        if( i >= p and i <= p + x - 1 and h1 != brush2[ i ] )
        {
            ans ++ ;
            h1 = brush2[ i ] ;
            p = i ;
        }
        if( i > p + x - 1 )
        {
            ans ++ ;
            h1 = brush2[ i ] ;
            p = i ;
        }
        ans2 += h[ i ] ;
        ans3 += brush2[ i ] ;
    }
    cout << ans2 - ans3 << "\n" << ans ;
    return 0;
}