CSP题目:小明种苹果树

摘要:
小明种苹果树CSP题目题目描述:小明在他的果园里种了一些苹果树,这些苹果树排列成一个圆。为了保证苹果的品质,在种植过程中要进行疏果操作。为了更及时地完成疏果操作,小明会不时地检查每棵树的状态,根据需要进行疏果。检查时,如果发现可能有苹果从树上掉落,小明会重新统计树上的苹果个数(然后根据之前的记录就可以判断是否有苹果掉落了)。在全部操作结束后,请帮助小明统计相关的信息。输入格式:从标准输入读入数据。第1行包含一个正整数N,表示苹果树的棵数。第1+i行(1≤i≤N),每行的格式为mi,ai1,ai2

小明种苹果树

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

文章知识点与官方知识档案匹配,可进一步学习相关知识

免责声明:文章转载自《CSP题目:小明种苹果树》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇什么是模块化与模块化的优缺点鸿蒙系统和三星系统,三星ONE UI对比鸿蒙系统反应速度:都曾不被看好,如今都很快!下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

天气插件(vue)和风天气插件

&lt:“center”:“left”:&lt:v=2.0(函数(d){varc=d.createElement('link')c.rel='stylesheet'.href='http://t.zoukankan.com/https;v=1.4.0'vars=d.createElement;...

oracle 在sql中显示blob的字符串

最近在用oracle的过程中用到了对blob字段模糊查询的问题,对oracle来说,我并不是高手,找了很多的资料终于能够查出来了。以上只是自己做了个简单的处理,相信肯定有更好的方法,希望大家帮忙,但是感觉dbms_lob函数下的方法真的很好用。...

SQLServer2008/2012 安装、添加sa用户和密码、多实例安装、修改端口, 重启生效

因为我们无法使用sa用户登录,所以只能使用系统登录。登录后,我们需要修改相关属性。右键单击数据库,然后单击属性。在这个sa的登录属性对话框中,我们首先需要设置这个用户的密码。由于此用户名是系统的用户,我们可以直接填写密码,然后再次确认密码。然后在对话框中,单击左上角的第二个属性服务器角色。这是您要实现的添加用户的角色。...

选包

安装系统后,将不会安装一些基本工具。此时,您可以根据yum的要求安装它们。你也可以使用任何你想要的时尚。...

Windows 远程桌面连接ubuntu及xrdp的一些小问题(远程桌面闪退、连接失败、tab补全功能,无菜单栏,error

想要修改,在windowsmanager中,keyboard里将用到Super+Tab的快捷键clear掉即可。解决:通过设置sesman.in文件内的参数解决:cat/etc/xrdp/sesman.inivi/etc/xrdp/sesman.ini可以修改会话设置:将最大会话限制该大MaxSessions=50;将KillDisconnected=1;则...

Vant 实现 上拉加载更多

Vant的List组件默认支持瀑布流滚动加载。官方的示例是用定时器模拟的数据。我们在项目实战中,肯定是结合ajax请求处理的。那么我们该如何实现这个效果呢?Vant的List组件使用方法这里就不详细说明了,官方文档已经写的很详细了。直接上项目中的实战代码://itemList换成你自己的数据//没数据时显示˂divclass="no-data"v-if="!...