题解：CF1635C Differential Sorting

Storm_Lightning · 2024-05-31 23:43:21 · 题解

CF1635C Differential Sorting 题解

题目大意

给定一个长度为 n 的序列 a[i]，然后再进行不超过 n 次操作，每次选三个数 x,y,z，然后执行 a[x]=a[y]-a[z] 的操作。若有解，则输出操作次数和每次操作的 x,y,z 即可。

思路分析

首先，我们可以对序列 a 进行分类讨论。

• 如果序列 a 是单调不减的，则输出 0 即可。

• 若 a 不是单调不减的，我们考虑若 a[n-1]>a[n]，则此时必定无解，因为这样的话 a[n-1] 的值就无法更新了。还有一点就是，若 a[n]<0 则无解，否则就可以将前面的数都修改为 a[n-1]-a[n]。

提示

• 本题多组数据。

• 要开 long long。

代码

int n,t;
int a[200010];
signed main()
{
    cin>>t;
    while(t--)
    {
        int flag=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(i>1&&a[i]<a[i-1])
            {
                flag=1;
            }
        }
        if(flag==0)
        {
            cout<<0<<endl;
            continue;
        }
        if(a[n-1]>a[n]||a[n]<0)
        {
            cout<<-1<<endl;
            continue;
        }
        cout<<n-2<<endl;
        for(int i=1;i<=n-2;i++)
        {
            cout<<i<<' '<<n-1<<' '<<n<<endl;
        }
    }
    return 0;
}

克制自己，不要抄代码！