题目

编号： 201909-2

试题名称： 小明种苹果（续）

时间限制： 1.0s

内存限制： 512.0MB

题目描述

小明在他的果园里种了一些苹果树，这些苹果树排列成一个圆。为了保证苹果的品质，在种植过程中要进行疏果操作。为了更及时地完成疏果操作，小明会不时地检查每棵树的状态，根据需要进行疏果。检查时，如果发现可能有苹果从树上掉落，小明会重新统计树上的苹果个数（然后根据之前的记录就可以判断是否有苹果掉落了）。在全部操作结束后，请帮助小明统计相关的信息。

输入格式

从标准输入读入数据。
第1行包含一个正整数$N$，表示苹果树的棵数。
第$1+i$行（$1\le i\le N$），每行的格式为$m_i, a_{i1}, a_{i2},\dots , a_{im_i}$。其中，第一个正整数$m_i$表示本行后面的整数个数。后续的$m_i$个整数表示小明对第$i$棵苹果树的操作记录。若$a_{ij}（1\le i \le m_i）$为正整数，则表示小明进行了重新统计该棵树上的苹果个数的操作，统计的苹果个数为$a_{ij}$；若为零或负整数，则表示一次疏果操作，去掉的苹果个数是$|a_{ij}|$。
输入保证一定是正确的，满足：

$a_{i1}>0$，即对于每棵树的记录，第一个操作一定是统计苹果个数（初始状态，此时不用判断是否有苹果掉落）；
每次疏果操作保证操作后树上的苹果个数仍为正。

输出格式

输出到标准输出。
输出只有一行，包含三个整数$T、D、E$。其中，

$T$为全部疏果操作结束后所有苹果树上剩下的苹果总数（假设每棵苹果树在最后一次统计苹果个数操作后苹果不会因为疏果以外的原因减少）；
$D$为发生苹果掉落的苹果树的棵数；
$E$为相邻连续三棵树发生苹果掉落情况的组数。
对于第三个统计量的解释：$N$棵苹果树$A_1，A_2, \dots ,A_N$排列成一个圆，那么$A1$与$A2$相邻，$A2$与$A3$相邻，$\dots$ ，$A_{N-1}$与$A_N$相邻，$A_N$与$A_1$相邻。如果$A_{i-1}，A_i，A_{i+1}$这三棵树都发生了苹果掉落的情况，则记为一组。形式化的，有 $E=|{A_i | Drop(Pred(A_i) \wedge Drop(A_i)\wedge Drop(Succ(A_i))}|$ 其中，$Drop(A_i)$表示苹果树$A_i$是否发生苹果掉落的情况，$Pred(A_i)$表示$A_i$的前一棵树$A_{i-1}$（如果$i>1$）或者$A_N$（如果$i=1$），$Succ(A_{i+1})$表示$A_i$的后一棵树$A_{i+1}$（如果$i<N$）
或者$A_1$（如果$i=N$）。

样例数据

样例1输入

4
4 74 -7 -12 -5 
5 73 -8 -6 59 -4
5 76 -5 -10 60 -2
5 80 -6 -15 59 0

样例1输出
222 1 0

样例1解释
全部操作结束后，第1棵树上剩下的苹果个数为$74-7-12-5=50$，第2棵为$59-4=55$，第3棵为$60-2=58$，第4棵为$59-0=59$。因此$T=50+55+58+59=222$。
其中，第3棵树在第2次统计之前剩下的苹果个数为$76-5-10=61>60$，因此发生了苹果掉落的情况。可以检验其他的树没有这种情况，因此$D=1$。
没有连续三棵树都发生苹果掉落的情况，因此$E=0$。

样例2输入

5
4 10 0 9 0
4 10 -2 7 0
2 10 0
4 10 -3 5 0
4 10 -1 8 0

样例2输出
39 4 2

样例2解释
第1、2、4、5棵树发生了苹果掉落的情况，因此$D=4$。其中，连续三棵树都发生苹果掉落情况的有（5，1，2）和（4，5，1），因此$E=2$。

子任务

编号	N	$max\\{ m_i \\}$
1，2	3	2
3，4	10	10
5，6	10	100
7，8	100	100
9，10	1000	1000

$m_i\le 1000$，对所有 $1\le i\le N$
$|a_{ij}| \le 10^6$，对所有 $1\le i\le N，1\le j\le m$；

提示

如果你的程序没有实现统计$D$和$E$的功能，请按照$D=0，E=0$输出结果，这样如果$T$的统计正确能够得到一部分分数。
如果你的程序没有实现统计$E$的功能，请按照$E=0$输出结果，这样如果$T$和$D$的统计正确能够得到一部分分数。

解答

分析

维护两个全局的变量（不是全局变量）T、D和一个掉果情况的数组tree，初始化tree全为0。然后读取输入数据模拟每一轮疏果的情况，一轮结束后统计和更新T、D，若发生过掉果则将该树掉果状态设为1。所有轮次结束后T、D获得最终结果。
此时再根据tree数组来逐个检查连续掉果情况，检查每棵树紧邻前一棵和后一棵的掉果情况。因为逻辑上所有树围成一个环形，为解决数组收尾相连的问题，索引始终加上数组长度，当索引前一棵数的时候将负数索引转到数组末尾，并使用模运算模以数组长度，使得最后一棵树索引向后越界的时候回到限定区域中来。

代码

#include <iostream>

#define MAXN 1001//果数总上限

using namespace std;

int main() {

	int N;//苹果树的棵数
	int T = 0;//全部疏果操作结束后所有苹果树上剩下的苹果总数
	int D = 0;//发生苹果掉落的苹果树的棵数
	int E = 0;//相邻连续三棵树发生苹果掉落情况的组数

	int tree[MAXN] = {0};//维护果树掉落情况的序列，便于之后计算连续情况。值为1代表掉落。

	cin >> N;//获取输入数据
	
	for (int i = 0; i < N; i++) {
		int m;//本行后面的整数个数
		int n;//本棵树上苹果个数
		cin >> m >> n;

		//由于已经将果树初试个数数据读入，所以m-1
		for (int j = 0; j < m-1; j++) {
			int t;
			cin >> t;
			if (t > 0) {
				//大于0代表重新统计了果数，与之前的对比，看是否有掉落，更新tree数组
				
				//n>t,说明发生了掉落,标记tree[i]
				if (n > t) {
					tree[i] = 1;
				}

				n = t;//将n更新为最新统计结果
			}
			else{
				//小于等于0，进行了疏果，更新当前个数
				n += t;//t小于0，所以用加号
			}
		}

		//本轮结束，累计总果数
		T += n;
	}
	
	//统计掉落的颗数和连续情况
	for (int i = 0; i < N; i++) {
		if (tree[i] > 0) {
			D++;

			//对tree索引进行 +N 和 %N 运算，放置越界
			if (tree[(i + 1) % N] > 0 && tree[(i - 1 + N) % N] > 0)
				E++;
		}
	}

	cout << T << " " << D << " " << E << endl;

	return 0;
}