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--;
    }
}