NOIP提高组【JZOJ4788】序列

Description

Data Constraint

我们设d[i]表示a[i]要经过多少次操作后才可到达b[i],设c[i]=d[i]-d[i-1]。那么最朴素的想法答案ans= ∑ni=1Max(0,c[i]) 。但这只是每个数都不会超过自己d[i]的情况，我们还要考虑假设某个数被某个区间包含，后来又多做了4次再次返回自已要求值的情况。显然对于现在的某段区间[i,j]，它多做了4次会使c[j]-4，使c[i]+4,那么我们再回想刚才的公式ans= ∑ni=1Max(0,c[i]) ，我们明显想使ans最小，也就是想使max（0，c[i]+4）+max(0,c[j]-4)

1：当c[j]为1时，显然max(0,c[i]+4)肯定不会比max(c[i],0)+1更小，所以无需考虑。

2：当c[j]为2时，我们发现只有c[i]=-3时才会使答案小1，所以我们看j之前是否有c[i]=-3的数，假设有，就将答案减1，并将c[i]=-3的数量-1，紧接着我们发现c[j]-4后值为-2,所以我们将c[i]=-2的数量+1。

3：当c[j]为3时，我们发现c[i]=-3时会使答案小2，而c[i]=-2时会使答案小1，所以我们看j之前是否有c[i]=-3的数，假设有，就将答案减2，并将c[i]=-3的数量-1。假设没有，我们再看看j之前是否有c[i]=-2的数，假设有，就将答案减1，并将c[i]=-2的数量-1。

4：对于c[j]<0的情况，明显他们对当前答案的贡献为0，所以无需做改变，只需将c[j]=-2的数量或c[j]=-3的数量+1即可。

总时间复杂度为O(N)。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=;
int a[maxn],b[maxn],d[maxn],n,i,t,j,k,l,x,y,ans,c[];
int main(){
//  freopen("data.in","r",stdin);
    scanf("%d",&l);
    while (l){
        scanf("%d",&n);
        for (i=;i<=n;i++)
            scanf("%d",&a[i]);
        for (i=;i<=n;i++)
            scanf("%d",&b[i]),d[i]=(b[i]+-a[i])%;
        t=;ans=;memset(c,,sizeof(c));
        for (i=n;i>=;i--)
            d[i]-=d[i-],ans+=max(,d[i]);
        for (i=;i<=n;i++){
            if (d[i]<-) c[-d[i]]++;
            else if (d[i]>){
                if (d[i]==){
                    if (c[]) c[]--,ans--,c[]++;
                }
                else if (d[i]==){
                    if(c[]) c[]--,ans-=;
                    else if (c[]) c[]--,ans--;    
                }
            }
        }
        printf("%d\n",ans);
        l--;
    }
}