题解：CF1635C Differential Sorting

xiaokang_suancai · 2024-08-07 22:21:46 · 题解

CF1635C 题解

题目传送门

题目大意

给定长为 n 的数组 a，最多执行 n 次操作，每次操作可以选择三个下标 x,y,z，使得 a_x=a_y-a_z。如果无解则输出 -1。

思路分析

首先是不需要执行任何操作的情况。显然，当 a 不是单调递减的时候，不需要操作，输出 0 即可。\ 其次是无解的情况。不难发现，如果 a_{n-1} > a_n 或者 a_{n-1}-a_n > a_{n-1}，我们不可能在规定次数内将数组变为非降序。\ 最后是一般情况。通过推理易证，只要在一般情况下的数组都恰好需要 n-2 次操作。我们只要在每一次循环中都使 a_i=a_{n-1}-a_n 就一定能将数组变为非降序。\ 一道不错的思维题。

参考代码

#include<bits/stdc++.h>
using namespace std;
int a[200005],t,n;
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        a[0]=-0x3fffffff; // 这里是为了防止在判定非降序时数组边界的随机数导致误判
        bool flag=true;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
        {
            if(a[i]<a[i-1])
            {
                flag=false; // 如果判定到有降序就直接跳过
                break;
            }
        }
        if(flag)
        {
            cout<<0<<endl;
            continue;
        } // 在非降序的情况下直接输出 0 
        if(a[n-1]>a[n])
        {
            cout<<-1<<endl;
            continue;
        }
        if(a[n-1]-a[n]>a[n-1])
        {
            cout<<-1<<endl;
            continue;
        } // 判断无解的情况，上面已经讲了 
        else
        {
            cout<<n-2<<endl;
            for(int i=1;i<=n-2;i++)
                cout<<i<<" "<<n-1<<" "<<n<<endl;
        } // 套用推导出来的公式
    }
    return 0;
}