Codeforces 1635C. Codeforces Round #772 (Div. 2) C(思维)
原题链接
简单
作者:
小小_88
,
2022-11-30 23:33:42
,
所有人可见
,
阅读 140
Differential Sorting
C++ 代码
/*
本题要求我们通过给定的操作将原序列变成不下降的
由于我们只能将 a[x] 变成 a[y] - a[z] (x < y < z)
因此不难发现,最后两个数是不可能改变的,因此如果最后两个数是逆序,直接可以判断无解
由于不限制操作次数,接下来就是要将剩下 n - 2 变成不下降的序列
对于 a[x],我们操作之后肯定是小于 a[y] 的,那么对于任何一个数,减去一个正数会变小,减 0 不变,
减去一个负数会变大,因此对于任意一组操作 (x, y, z),我们都要保证 a[z] 是个非负数,这样才能保证
操作之后 a[x] <= a[y],要想知道序列中是否存在一个非负数 a[z],因为序列的非下降性,因此只需要看
a[n] 是不是非负数即可,如果 a[n] 是负数,那么任意一个操作 a[x] = a[y] - a[z],都会让 a[x] > a[y],
此时不可能得到任意一组解。如果 a[n] 是非负数,那么我们就可以固定 a[z] 为 a[n],这样任意一组操作
a[x] = a[y] - a[z] 都能保证 a[x] <= a[y],这样我们就可以构造出一个解,我们从 a[n - 2] 开始从后往
前处理每个数,对于每个数 a[i],我们令 a[i] = a[i + 1] - a[n],等前 n - 2 个数都执行完此操作,对于
任意一个数 a[i],都能保证 a[i] <= a[i + 1],这就是一个合法的解。
综上所述,我们看一下原序列,如果序列有序,不需要操作,如果序列无序且 a[n] < 0,则一定无解,
如果序列无序且 a[n] >= 0,则按照上述方法一定能得到一组解。
*/
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 200010;
typedef pair<int, int> PII;
int n;
int a[N];
void check()
{
if(a[n] < 0)
{
for(int i = 1; i < n; i++)
if(a[i] > a[i + 1])
{
puts("-1");
return;
}
puts("0");
return;
}
if(a[n - 1] > a[n])
{
puts("-1");
return;
}
printf("%d\n", n - 2);
for(int i = n - 2; i >= 1; i--)
printf("%d %d %d\n", i, i + 1, n);
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
op.clear();
check();
}
return 0;
}