题解：P7697 [COCI2009-2010#4] OGRADA

Hrz_OIer · 2024-04-17 12:16:00 · 题解

~~P5186 和这道题怎么一模一样~~

思路

先考虑第一问

显然这是个“滑动窗口”的模型。

但是把每个滑动窗口刷的面积加起来并不是答案，因为一个位置可能会多次刷。

考虑删去重复部分，当上一个滑窗高度为 last，这个为 now 时，容易发现重合的部分为：

\min \{{ last , now \}} \times (x − 1)

据此，就容易统计了。

code:

//初始 sum 为木板高度和
    int lstans=0;
    for(int i=1;i<=n;++i){
        while(head<=tail&&a[q[tail]]>a[i])tail--;
        while(head<=tail&&q[head]<=i-x)head++;
        q[++tail]=i;
        if(i>=x)
            mx[i-x+1]=a[q[head]]，//记录区间 [i-x+1,i] 的最小值，第二问用
            sum-=1ll*x*a[q[head]],
            sum+=1ll*min(a[q[head]],lstans)*(x-1),
            lstans=a[q[head]];}

考虑第二问

我们记第一问求得区间 [i, i + x − 1] 的最小值为 mx_i 。则位置 i 被刷的高度 color_i 为：

color_i = \max \{{mx_i−x+1, mx_i−x+2, · · · , mx_i\}}

这又是个单调队列的式子，可以单调队列优化。

最后，我们知道了每个位置要刷的高度，要求刷的次数。则用贪心可求出：

若 color_i \ne color_i−1，则肯定要分开来刷。
若有 k 个刷的高度相同的连续位置，要刷 \big\lceil \frac{k}{x} \big\rceil 次。

这样统计就行了。

code：

    for(int i=1;i<=n;++i){
        while(head<=tail&&mx[q[tail]]<mx[i])tail--;
        while(head<=tail&&q[head]<=i-x)head++;
        q[++tail]=i;
        brush[i]=mx[q[head]];}//记录刷的高度 
    int beg=-10000000,cnt=0;
    for(int i=1;i<=n;++i)
        //判断高度是否等于上一个，或者是太长刷不到了 
        if(brush[i]!=brush[i-1]||i>=beg+x)cnt++,beg=i;

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
#define int long long
int mx[N],q[N<<1],a[N],x,n,brush[N],head,tail,sum;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;++i)cin>>a[i],sum+=a[i];
    int lstans=0;
    for(int i=1;i<=n;++i){
        while(head<=tail&&a[q[tail]]>a[i])tail--;
        while(head<=tail&&q[head]<=i-x)head++;
        q[++tail]=i;
        if(i>=x)
            mx[i-x+1]=a[q[head]],
            sum-=1ll*x*a[q[head]],
            sum+=1ll*min(a[q[head]],lstans)*(x-1),
            lstans=a[q[head]];}
    for(int i=1;i<=n;++i){
        while(head<=tail&&mx[q[tail]]<mx[i])tail--;
        while(head<=tail&&q[head]<=i-x)head++;
        q[++tail]=i;
        brush[i]=mx[q[head]];}
    int beg=-10000000,cnt=0;
    for(int i=1;i<=n;++i)if(brush[i]!=brush[i-1]||i>=beg+x)cnt++,beg=i;
    cout<<sum<<"\n"<<cnt;
    return 0;}

制作不易，点个赞吧！（ QAQ ）