Codeforces 1753A1. Codeforces Round #829 (Div. 1) A1(思维)
原题链接
简单
作者:
小小_88
,
2022-12-01 22:57:37
,
所有人可见
,
阅读 196
Make Nonzero Sum (easy version)
C++ 代码
/*
本题要将整个序列合并成若干个区间,每个区间中的数正负交替,要求所有数的和为 0 的一种划分方案
首先如果是奇数个数,那么无论怎么划分区间,都会有一个奇数个的区间影响正负数的平衡,因此奇数个数一定无解。
对于偶数个数,我们可以先将所有数两个两个的划分开,到此每个数的正负性还和原先没有区别。
对于每个两个数的区间 a[i] 和 a[i + 1],如果 a[i] = a[i + 1],此时他们两个的和就是 0。如果
a[i] != a[i + 1],此时我们可以再将区间分成各自一组,那么 a[i] 和 a[i + 1] 就都是正的,而两个
数不同代表一定是一个 1 一个 -1,因此此时再相加结果也就是 0 了,按照这个方法将所有数两两划分,
再将不同的各自作为单个区间,一定能让所有数的和变成 0。
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200010;
int n;
int a[N];
int l[N], r[N], cnt;
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
cnt = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
if(n & 1)
{
puts("-1");
continue;
}
for(int i = 1; i <= n; i += 2)
if(a[i] == a[i + 1])
l[++cnt] = i, r[cnt] = i + 1;
else
l[++cnt] = i, r[cnt] = i, l[++cnt] = i + 1, r[cnt] = i + 1;
printf("%d\n", cnt);
for(int i = 1; i <= cnt; i++) printf("%d %d\n", l[i], r[i]);
}
return 0;
}