题目

---

解题思路

我们设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])∑i=1nMax(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)。

引用于：https://blog.csdn.net/crybymyself/article/details/52587755

---

代码

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int tt,n,a[101000],b[101000],ans=2147483647,q,t[5]; int main(){ scanf("%d",&tt); while (tt--){ scanf("%d",&n); ans=0; memset(t,0,sizeof(t)); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++){ scanf("%d",&q); b[i]=(q-a[i]+4)%4; ans+=max(b[i]-b[i-1],0); } for (int i=2;i<=n;i++){ int g=b[i]-b[i-1]; if (g>0) { if (t[1]&&g>1) t[1]--,t[g]++,ans-=g-1; else if (t[2]&&g>2) t[2]--,t[g]++,ans-=g-2; } else t[g+4]++; } printf("%d\n",ans); } }