小明种苹果树
CSP题目
题目描述：小明在他的果园里种了一些苹果树，这些苹果树排列成一个圆。为了保证苹果的品质，在种植过程中要进行疏果操作。为了更及时地完成疏果操作，小明会不时地检查每棵树的状态，根据需要进行疏果。检查时，如果发现可能有苹果从树上掉落，小明会重新统计树上的苹果个数（然后根据之前的记录就可以判断是否有苹果掉落了)。在全部操作结束后，请帮助小明统计相关的信息。
输入格式：
从标准输入读入数据。
第1行包含一个正整数N，表示苹果树的棵数。
第1+i行（1≤i≤N)，每行的格式为mi,ai1,ai2,… ,aimi,。其中，第一个正整数mi表示本行后面的整数个数。后续的mi个整数表示小明对第i棵苹果树的操作记录。若aij (1≤ j ≤mi）为正整数，则表示小明进行了重新统计该棵树上的苹果个数的操作，统计的苹果个数为aij;若为零或负整数，则表示一次疏果操作，去掉的苹果个数是|aij|。
输入保证一定是正确的，满足:
a.ai1>0，即对于每棵树的记录，第一个操作一定是统计苹果个数（初始状态，此时不用判断是否有苹果掉落）；
b.每次疏果操作保证操作后树上的苹果个数仍为正。
输出格式：
输出到标准输出。
输出只有一行，包含三个整数T、D、E。其中，
a.T为全部疏果操作结束后所有苹果树上剩下的苹果总数（假设每棵苹果树在最后一次统计苹果个数操作后苹果不会因为疏果以外的原因减少);
b.D为发生苹果掉落的苹果树的棵数;
c.E为相邻连续三棵树发生苹果掉落情况的组数。
对于第三个统计量的解释：N棵苹果树A1,A2,…,AN排列成一个圆，那么A1与A2相邻，A2与A3相邻，…，AN-1与AN相邻，AN与A1相邻。如果Ai-1, Ai，Ai+1这三棵树都发生了苹果掉落的情况，则记为一组。形式化的，有
E=|{Ai/Drop(Pred(Ai)）∧Drop(Ai）∧Drop(Succ(Ai)）}|
其中，Drop(Ai）表示苹果树Ai是否发生苹果掉落的情况，Pred(Ai)表示Ai的前一棵树Ai-1（如果i>1）或者AN（如果i=1)，Succ(Ai)表示Ai的后一棵树Ai+1（如果i<N）或者A1（如果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。
c++代码如下：
#include <iostream>
#include <stdlib.h>
using namespace std;
#define ListInitSize 256//初次分配空间大小
#define ListIncrement 128//空间分配增量大小
typedef struct List
{
int *pData;//动态存储空间的基地址
int length;//存储数据元素的个数
int size;//当前已分配的存储空间的大小
}List;
void InitList( List &L )
{//初始化顺序表
L.pData = (int *)malloc(ListInitSize * sizeof(int));//申请存储空间
if( L.pData == NULL )
exit(1);//存储空间申请失败
L.size = ListInitSize;//当前已分配的存储空间大小
L.length = 0;//存储数据元素个数为零
}//InitList
typedef struct LNode
{
int data;//数据域
struct LNode *next;//指针域
} LNode, *LinkList;
typedef struct SListInfo
{
LinkList head;//表头结点指针
LNode *pCurNode;//当前结点指针位置
LNode *pre;//当前结点的前驱结点指针位置
LNode *next;//当前结点的后继结点指针位置
int length;//单链表的长度（元素个数）
} SListInfo;
void InitList( SListInfo &L )
{//初始化单链表
L.head = (LNode *)malloc(sizeof(LNode));//申请头结点存储空间
if( L.head == NULL )
cout<<"error1"<<endl;//存储空间申请失败
L.head->next = NULL;//头结点后无其他结点
L.pCurNode = L.head;//当前指针也指向头结点
L.pre = L.head;//前驱指针也指向头结点
L.next = L.head;//后继指针也指向头结点
L.length = 0;//单链表长度为零
}//InitList
void InsertElem( SListInfo &L, int i, int e )
{//在第i个位置后插入新的数据元素e
LNode *s = (LNode *)malloc(sizeof(int));//申请新的结点
if( s == NULL )
cout<<"error2"<<endl;;//申请失败
s->data = e; //将e存入新结点
L.pCurNode = L.head;
for( ; i > 0; i -- )//找到位置i
{
if( L.pCurNode->next == NULL)
{
cout<<"error3"<<endl;
break;
}
L.pCurNode = L.pCurNode->next;
}
if( L.pCurNode->next != NULL)
{
s->next = L.pCurNode->next;//插入元素e
L.pCurNode->next = s;
L.length += 1;//链表长度+1
}
else
{
L.pCurNode->next = s;
s->next = NULL;
L.length += 1;
}
}//InsertElem
int AppleNumber( SListInfo &L, List &La, int j )
{//统计该棵苹果树的苹果个数
int i, sum = La.pData[1];
L.pCurNode = L.head->next;
for( i = 1; i < j - 1; i ++ )//将L.pCurNode置于当前棵数结点
{
L.pre = L.pCurNode;
L.pCurNode = L.pCurNode->next;
L.next = L.pCurNode->next;
}
for( i = 2; i <= L.length; i ++ )
{
if( La.pData[i] > 0 )//重新统计了苹果个数
{
sum = La.pData[i];
if( sum < La.pData[0] )//有苹果掉落
{
L.pCurNode->data = -1;
}
}
else//进行了疏果操作
{
sum = sum + La.pData[i];
}
}
cout<<sum<<endl;
return sum;
}
int AppleFall( SListInfo &L )
{//计算发生苹果掉落的苹果树的棵数
int i = 0;
L.pCurNode = L.head->next;
while( L.pCurNode != NULL )
{
if( L.pCurNode->data < 0 )//有苹果掉落
{
i ++;
}
L.pCurNode = L.pCurNode->next;
}
return i;
}
int AppleFallGroup( SListInfo &L )
{//计算三棵树发生苹果掉落情况的组数
int i = 0;
L.pCurNode = L.head;
L.next = L.pCurNode;
L.pre = L.pCurNode;
while( L.next != NULL)
{
if( L.pCurNode->data < 0 && L.pre->data < 0 && L.next->data < 0)
{
i ++;
}
L.pre = L.pCurNode;//往后移
L.pCurNode = L.pCurNode->next;
L.next = L.pCurNode->next;
}
return i;
}
int main()
{
SListInfo L;
List La;
int i, N, j, T = 0, D, E, m, k = 1;
int &e = k;
cout<<"-进行初始化操作-"<<endl;
InitList(L);//分别初始化链表和顺序表
InitList(La);
cout<<"请输入一个正整数N，表示苹果树的棵数"<<endl;
cin>>N;
for( i = 0; i <= N; i ++ )//每一个结点表示一棵苹果树
{
InsertElem(L, i, e);//将数据全都设置为1，表示苹果树的状态
}
cout<<"在接下来的"<<N<<"行里，请依次输入m和m个数ai表示苹果树的记录"<<endl;
for( i = 0; i < N; i ++ )
{
cin>>m;
for( j = 1; j <= m; j ++ )
{
cin>>La.pData[j]; //用顺序表存储单棵苹果树的状态
}
T = T + AppleNumber( L, La, j );//苹果总数
}
D = AppleFall(L);
E = AppleFallGroup(L);
cout<<"-操作结束-"<<endl;
cout<<T<<" "<<D<<" "<<E;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
文章知识点与官方知识档案匹配，可进一步学习相关知识