CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes), problem: (D) Magical Array

一.题意：

给你一个数组，其中有m个元素，下面由两种操作。

type 1:

选择数组中两个位置的元素i和j（i<j），使得这两个位置元素大小减1，并且使得位置i-1和位置j+1的位置的元素加1

type 2: 

选择数组中两个位置的元素i和j（i<j），使得这两个位置元素大小减1，并且使得位置i-1和位置j+2的位置的元素加1

你要通过这两种操作使得原数组变化获取m个新数组，但是要求每个新数组的获取必须用且仅用一种上面的操作（种类限制一种，但是操作次数不限）。由于这m个数组中有且仅有一个数组用的是type2操作，所以我们称它为特殊数组，现在要求你从这m个数组中找出这个用的是type2操作的特殊数组，并且求出用了多少次type2操作。

二.思路：

我们可以看出来，其实type1操作，就是将一个数左移一个数右移，而type2操作相当于把一个数左移，一个数右移两次。所以用type1操作形成的新数组左移右移相等，而用type2操作形成的新数组左移右移次数不相等，如果进行了k次type2操作那么，右移-左移=k。

既然这样我们可以选取m个新数组中的第一个作为参照物，然后不断地对下面的数组从i=1开始进行左移右移操作，使得这两个数组相等，然后看左移右移次数是否相等。

如果不等，有两种情况：
1.参照物数组是特殊数组

2.此数组是特殊数组

如此分类讨论即可。

三.代码

#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
const int N=3E5+10;
typedef long long LL;
LL a[N];
LL b[N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i];//将第一个数组作为参照物
    }
    int pos=0;//存哪个是特殊数组
    LL mov=0;//存特殊数组进行了几次操作
    for(int i=2;i<=n;i++)
    {
        
        LL move=0;
        for(int j=1;j<=m;j++)
        {
            cin>>b[j];
        }
        for(int j=1;j<=m;j++)
        {
            
            if(b[j]>a[j])//当前比参照物大 进行右移
            {
                move+=b[j]-a[j];
                b[j+1]+=b[j]-a[j];
                b[j]=a[j];
            }
            else if(b[j]<a[j])//当前比参照物小 进行左移
            {
                move-=a[j]-b[j];
                b[j+1]-=a[j]-b[j];
                b[j]=a[j];
            }
        }
        if(move!=0&&!pos)
        {
            pos=i;
            mov=move;
        }
        else if(move!=0&&pos)//多于1次move不是0（左移右移不等）了，那么参照物是特殊数组
        {
            pos=1;
        }
        
    }
    cout<<pos<<' '<<abs(mov)<<endl;
    
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
}