游戏（game）

题目描述

 

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

 

输入

 

第一行一个T 表示数据组数。

对于每组数据，第一行两个整数表示序列长度和模数。

接下来两行分别包含n 个整数，表示初始序列和目标序列。

 

输出

 

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

 

样例输入

16 41 1 3 2 0 22 0 2 3 2 0

样例输出

4

提示

 

样例解释

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

数据范围

1≤T≤51≤T≤5

对于10% 的数据满足n≤1n≤1

对于30% 的数据满足n≤10n≤10

对于50% 的数据满足n≤100n≤100

对于70% 的数据满足n≤5000n≤5000

对于100% 的数据满足1≤n≤100000,1≤k≤100,0≤x1≤n≤100000,1≤k≤100,0≤x(序列中的任一数)<k<k

 

来源

---

solution

首先我们可以求出每一个位置需要操作几次。

设为a[i].记c[i]=a[i]-a[i-1]

我们可以把a[i]的连续一段加上k

相当于把位置+k 另一个位置-k

我们应该要把一个大于零的减掉k，小于零的加k使答案更优

于是用一个桶存下小于零的，每次取尽量小即可

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define maxn 100005using namespace std;int T,n,k,a[maxn],t,f[maxn],g[maxn],c[maxn],tax[202],ans;int main(){ cin>>T; while(T--){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++){ scanf("%d",&t); int ne=t-a[i];ne=(ne+k)%k; a[i]=ne; } a[0]=0; for(int i=1;i<=n;i++)c[i]=a[i]-a[i-1];ans=0; memset(tax,0,sizeof tax); for(int i=1;i<=n;i++){ if(c[i]<0)tax[c[i]+k]++; else { bool fl=0; for(int j=0;j