DTOJ 3999 ♂U♂ Xi♂

$♂U ♂ Xi ♂$♂U♂Xi♂
时间限制: 1 Sec 内存限制: 256 MB

题目描述
这个游戏是这样的，你有一个初始序列S ，你每次可以选择一段任意长度的连续区间，把他们$+1$+1 再膜$k$k，给定目标序列，你需要尝试用尽量少的操作次数将初始序列变为目标序列。作为一名优秀的$OIer$OIer，您认为这个游戏十分$naive$naive，所以您打算撸一个游戏脚本来取到最优解。

输入

第一行一个T 表示数据组数。
对于每组数据，第一行两个整数表示序列长度和模数。
接下来两行分别包含n 个整数，表示初始序列和目标序列。

输出
对于每组数据，输出一行一个整数表示最少操作次数。

样例输入
1
6 4
1 1 3 2 0 2
2 0 2 3 2 0
样例输出
4
提示
样例解释

四次操作的一种方式为:$(1,6)(2,3)(2,3)(5,6)$(1,6)(2,3)(2,3)(5,6)

数据范围

$1≤T≤5$1≤T≤5
对于$10\%$10% 的数据满足 $n≤1$n≤1
对于$30\%$30% 的数据满足 $n≤10$n≤10
对于$50\%$50% 的数据满足 $n≤100$n≤100
对于$70\%$70% 的数据满足 $n≤5000$n≤5000
对于$100\%$100% 的数据满足 $1≤n≤100000$1≤n≤100000,$1≤k≤100$1≤k≤100,$0≤x$0≤x(序列中的任一数)$&lt;k$<k

题解：

若k==0,就变成了一道经典的贪心BZOJ3043
并且有hzwer的题解（建议大家先写写这题 虽然要权限 ）
考虑在$MOD k$MODk下的意义，可以无代价地将某个区间$+k$+k。
将它差分完之后，设差分后的序列为$c_{i}$ci​，
对于一个区间加 $d$d，等价于$c_{l}+d$cl​+d 与 $c_{r}-d$cr​−d
然后对于某个点，若要将它作为某个区间的左端点，一定要$a_{l}&lt;0$al​<0
才会更优秀。
从左向右扫$c$c数组，将$c_{i}+k(c_{i}&lt;0)$ci​+k(ci​<0)存入桶中,对于$&gt;0$>0的$c_{i}$ci​在桶中查找能减少的最大值,如果找到则更新桶,可以证明这个贪心是正确的复杂度$O(nk)$O(nk)
这还有一位神犇的博客
讲的也是这题。

#include<bits/stdc++.h>
using namespace std;
#define in inline
#define re register
#define rep(i,a,b) for(re int i=a;i<=b;i++)
#define repd(i,a,b) for(re int i=a;i>=b;i--)
#define For(i,a,b) for(re int i=a;i<b;i++)
#define _(d) while(d(isdigit(ch=getchar())))
template<class T>in void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;}
const int N=1e5+4;
int x1[N],x2[N],a[N],c[N],b[N],n,k,b1[N];
in void work(){
    memset(b,0,sizeof(b));
    g(n);g(k);int ans=0;
    rep(i,1,n) g(x1[i]);
    rep(i,1,n) g(x2[i]);
    rep(i,1,n) a[i]=x2[i]-x1[i],a[i]<0?a[i]+=k:a[i];
    repd(i,n,1) c[i]=a[i]-a[i-1];
    rep(i,1,n){
        if(c[i]>0){
            int pos=0;
            For(j,1,c[i]){
                if(b[j]){
                    pos=j;
                    break;
                }
            }
            if(pos) b[pos]--,b[c[i]]++,ans+=pos;
            else ans+=c[i];
        }
        else b[c[i]+k]++;
    }
    printf("%d\n",ans);
}
int main(){
    //freopen(".in","r",stdin);freopen(".out","w",stdout);
    int T;g(T);
    while(T--) work();
    return 0;
}