当前位置：文档库 › 第2部分语言提高班

第2部分语言提高班

第2部分语言提高班 (2)

2.1 数组与字符串（曹爱华） (2)

2.2 顺序查找（刘雪） (16)

2.3 结构体与排序（刘雪） (27)

2.4 枚举算法（冷学农） (46)

2.5递推与递归（冷学农） (60)

2.6 高精度计算（马风云） (79)

2.7 综合应用（马风云） (91)

第2部分语言提高班

2.1 数组与字符串（曹爱华）

知识点

掌握数组和字符串相关知识与应用，能灵活解决具体实际问题。

2.1.1 知识讲解

数组：数组是有序集合，包含的元素是由数组名和下标来唯一标识的；

一维数组的定义格式：类型标识符数组名[常量表达式]

说明：

①数组名的命名规则与变量名的命名规则一致。

②常量表达式表示数组元素的个数，就是数组的长度。是常量或者是符号常量，不能是变量。

例如：

int a[10]; int a[2*5]; //数组a定义是合法的

数组不能通过变量n来动态的调节数组的大小。例如：

int n;

cin>>n;

int b[n];

数组b定义是非法的。

int a[10] 定义了一个整型数组，数组名a,包括10个元素。10个元素分别依次是：a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]。a[10] 不属于这个数组范围了。

③同一数组的元素有相同类型属性；一个数组占用一片连续空间存储单元。

例如：一个整型数组a，有10个元素，起始地址为2000，a数组在内存的存储如图：

2000 2002 2004 2006 2008 2010 2012 2014 2016 2018 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

④数组之间不能整体赋值。例如：int a[10],b[10]; a=b; //这样赋值不合法。

⑤一维数组的初始化。格式：类型标识符数组名[常量表达式]={值1，值2，…}

int a[5]={1,2,3,4,5}; //依次赋值；

int a[10]={1,2,3,4,5}; // 仅仅对前5个数组赋值。

int a[10]={0}; //将10个元素初始化为0；

例2.1.1 输入n个整数,要求程序按输入时的逆序把这n个数打印出来，输入的整数不超过50个。

分析：用数组来处理多个数值。通过for循环语句输入，赋值给数组元素；调整for循环语句逆序输出。

#include

using namespace std;

const int N=50;

int a[N];

int main( )

{ int n;

cin>>n;

for(int i=0;i

cin>>a[i]; //scanf(“%d”,&a[i])；格式化输入

for(int i=n-1;i>=0;i--) //

cout<

return 0;

}

说明：int a[N]; 定义数组a是合法的，N是一个常变量，只读不能写，是定值50；数组a包括50个整型元素，a[0],a[1],……a[49],没有a[50];数组a被声明在main函数的外面,如果数组很大，放在main函数内部会异常退出。

例2.1.2用数组来处理斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34……前20项。

分析：通过观察，发现第三个数是前两个数之和f[i]=f[i-2]+f[i-1]，注意初始化第1 、2个数分别为1。

代码参考：

#include

using namespace std;

int main( )

{ int i;

int f[20]={1,1};

for(i=2;i<20;i++)

f[i]=f[i-2]+f[i-1];

for(i=0;i<20;i++)

{if(i%5==0) cout<

cout<

}

cout<

return 0;

}

说明：setw()数控制输出场宽，调用setw函数需注明使用头文件iomanip，注意控制换行使用技巧。

例2.1.3 某学校有n盏灯(n为不大于2000的正整数)，从1到n盏灯依次编号为1到n，初始状态为全部开启；有m个学生(m小于等于n的正整数),并且从1到m依次编号。第一个学生(1号学生)将灯全部关闭，第二个人(2号学生)将编号为2的倍数的灯打开，第三个人(3号学生)将编号为3的倍数的灯做相反处理（将开的灯关闭，关的灯打开）。依照编号递增顺序，以后的人都和他们一样，将自己编号倍数的灯都做相反处理。请问：当第m个人操作之后，哪几盏灯是关灯状态，由小到大输出其编号，其间用空格间隔。

输入:

输入正整数n和m，以单个空格隔开。

输出:

顺次输出关闭的灯的编号，其间用空格间隔。

样例输入:

8 3

样例输出:

1 5 6 7

分析：通过数组a[1]、a[2]、a[3]……a[n]分别表示序号为1、2、3……n盏灯的状态。模拟即可。

代码参考：

#include

using namespace std;

int a[2001];

int main()

{

int i,j,n,m;

memset(a,0,sizeof(a));

scanf("%d%d",&n,&m);

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

if(j%i==0)

a[j]=!a[j];

for(j=1;j<=n;j++)

if(a[j]==1)

printf("%d ",j);

return 0;

}

说明：sizeof函数需要cstring头文件；memset(a,0,sizeof(a))的作用是把数组a清零，当然也可以通过for循环来实现。

2.1.2 知识讲解

二维数组：

定义和引用：有两个下标的数组为二维。有些数据需要两个因素才能唯一确定，例如：有4个学生，每人有7门课程，第2个学生的第4门成绩，可以用a[2][4]来表示。

定义二维数组的一般形式为：

类型标识符数组名［常量表达式］［常量表达式］

例如：int a[3][4];

a数组实质上是一个有3行、4列的表格，表格中可储存12个元素。

a[0][0] a[0][1] a[0][2] a[0][3]

a[1][0] a[1][1] a[1][2] a[1][3]

a[2][0] a[2][1] a[2][2] a[2][3]

说明：第1行第1列对应a数组的a[0][0]，第n行第m列对应数组元素a[n-1][m-1]；当定义的数组下标有多个时，称为多维数组。可以把数组a看成有3个元素，每一个元素又是一个一维

数组，包含着4个元素，由数组的数组构成；数组的元素在内存中按行存放的。

二维数组的初始化

二维数组的初始化和一维数组类似。可以将每一行分开来写在各自的括号里，也可以把所有数据写在一个括号里。

例如：int a[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; // 分别对4行元素赋值 int a[4][2] = {1,0,0,1,-1,0,0,-1}; //尽量不要使用，容易混淆

int a[4][3]={{1},{2,2},{3},{4}}; //部分元素赋值，数组元素如下图：

1 0 0

2 2 0

3 0 0

4 0 0

int a[][4]={{1,2},{1},{},{1,6}};//通知编译系统数组有4行，数组元素赋值如下图： 1 2 0 0

1 0 0 0

0 0 0 0

1 6 0 0

【例题分析】

例2.1.4

有个n*m的矩阵(整数n<20, 整数m<20),通过键盘输入n*m个整数，整数小于1000；

求其中最大整数以及其所在行号和列号。

输入样例：

5 5

1 2 3 4 5

4 2 3 4 5

1 2 3 4 5

6 2 9 4 5

3 2 3

4 5

输出样例：

9 3 2

分析：假定第1个元素a[0][0]为最大值，max=a[0][0]，通过双层循环按照行的顺序把矩阵元素逐个和max比较，大于max就把元素的值赋给max，同时记录行号和列号，比较过的元素中max存放其中最大者，循环结束后，max自然记录的是最大值。

代码参考：

#include

using namespace std;

int a[21][21];

int main( )

{

int n,m,h,l,max;

scanf("%d%d",&n,&m); //输入行列

for(int i=0;i

for(int j=0;j

scanf("%d",&a[i][j]); //输入矩阵数组元素

max=a[0][0];

for(int i=0;i

for(int j=0;j

if(a[i][j]>max)

{max=a[i][j];

h=i;l=j;

}

printf("%d %d %d",max,h,l);//注意数据间的空格

return 0;

}

例2.1.5 蛇形矩阵

在n*n方阵里填入1,2,3,…,n*n，要求填成蛇形。例如n=4时方阵如下图：

上面的方阵，多余的空格只是为了便于观察规律，没有具体要求。n<=10。

分析：首先找规律，起始1在0行，n-1列，然后下、左、上、右的次序增大赋值到n*n。参考程序：

#include

using namespace std;

int a[11][11];

int main()

{

int n,i,j,s=1;

memset(a,0,sizeof(a));

scanf("%d",&n);

i=0;j=n-1; //起始位置

a[i][j]=1; //赋初值

while(s

{

while(i+1

while(j-1>=0&&!a[i][j-1]) a[i][--j]=++s;

while(i-1>=0&&!a[i-1][j]) a[--i][j]=++s;

while(j+1

}

for(i=0;i

{for(j=0;j

printf("%4d",a[i][j]);

printf("\n");

}

return 0;

}

说明：本程序通过第1个while语句控制范围大小，思考为什么不能等于n*n?然后通过4个while语句控制赋值的方向，下、左、上、右的次序，一定注意边界。仅仅通过几个简练语句，蛇形既出。

课后训练

训练1 校门外的树（Noip2005普及组第2题）

【问题描述】

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入:

第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

对于20%的数据，区域之间没有重合的部分；对于其它的数据，区域之间有重合的情况。输出:

包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

样例输入: 样例输出:

500 3 298

150 300

100 200

470 471

参考代码：

#include

using namespace std;

const int N=100010;

int a[N];

int l,n;

int main()

{

scanf("%d%d",&l,&n);

for(int i=1;i<=n;i++)

{

int x,y;

scanf("%d%d",&x,&y);

for(int j=x;j<=y;j++) a[j]=1; // 将有树的地方全赋值为1 表示有树}

int ans=0;

for(int i=0;i<=l;i++)

if (a[i]==0) ans+=1;

cout<

return 0;

}

训练2图像旋转(NOI题库/ 1.8编程基础之多维数组/11:图像旋转)

【问题描述】

输入一个n行m列的黑白图像，将它顺时针旋转90度后输出。

输入

第一行包含两个整数n和m，表示图像包含像素点的行数和列数。1 <= n <= 100，1 <= m <= 100。

接下来n行，每行m个整数，表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开，每个元素均在0~255之间。

输出

m行，每行n个整数，为顺时针旋转90度后的图像。相邻两个整数之间用单个空格隔开。样例输入

3 3

1 2 3

4 5 6

7 8 9

样例输出

7 4 1

8 5 2

9 6 3

参考代码：

#include

using namespace std;

int a[105][105];

int main()

{

int n,m;

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

{

int x;

scanf("%d",&x);

a[j][n-i+1]=x; // 此处就是将矩阵旋转90度存储

}

for(int i=1;i<=n;i++)

{

for(int j=1;j<=m;j++)

cout<

}

return 0;

}

2.1.4 知识讲解

字符数组

字符数组具有数组的公共属性，是用来存放字符数据的。

1、字符数组的定义格式

char 数组名[常量表达式]

例如：char c1 [5]; //数组ch1是一个具有5个字符元素的一维字符数组

//c1[0],c1[1],c1[2],c1[3],c1[4]共5个字符。 char c2[3][4]; //数组ch2是一个具有12个字符元素的二维字符数组

2.字符数组的赋值

字符数组赋值分为数组的初始化和数组元素的赋值。初始化的方式为：字符初始化和字符串初始化。

(1).用字符初始化数组

例如：

char c1[5]={‘c’,‘h’,‘i’,‘n’,‘a’};

初始值表中的每个数据项是一个字符，用字符给数组c1的各个元素初始化。当初始值个数少于元素个数时，从首元素开始赋值，剩余元素默认为空字符。

字符数组中也可以存放若干个字符，也可以来存放字符串。两者的区别是字符串有一结束符(‘\0’)。在一维字符数组中存放着带有结束符的若干个字符称为字符串。

字符串是一维数组，但是一维字符数组不等于字符串。

例如：

char c2[6]={ c’,‘h’,‘i’,‘n’,‘a’,‘\0’};在数组c2中存放着一个字符串“china”。

用cin、cout对字符数组的输入输出

Char str[10];

Cin>>str; //输入一个字符串，系统自动在后面加一个结束符‘\0’。不能超过数组长度。

Cout<

用其他方法对字符数组的输入输出

字符串作为一个整体进行输入和输出的语句。

1、输入

从键盘输入一个字符数组可以使用scanf语句或gets语句。

(1)scanf语句

格式：scanf(“%s”,字符数组名称);

说明：

①这里的字符数组名称之前可加可不加&这个取地址符。

②系统会自动在输入的字符串常量后添加‘\0’标志，因此输入时，仅输入字符串的内容即可。

③输入多个字符串时，以空格分隔。

例如：scanf(“%s%s%s”,s1,s2,s3)；从键盘分别输入Let us go，则三个字符串分别获取了三个单词。仅有一个输入字符串名称的情况下，字符串变量仅获取空格前的内容。

例如：scanf(“%s”,s1)；从键盘分别输入Let us go，则仅有第一个单词被获取，即s1变量仅获取第一个单词Let。

(2)gets语句

格式：gets(字符串名称)；

说明：使用gets只能输入一个字符串。

例如：gets(s1,s2)；是错误的。使用gets，是从光标开始的地方读到换行符也就是说读入的是一整行，而使用scanf是从光标开始的地方到空格，如果这一行没有空格，才读到行尾。

例如：scanf(“%s”,s1)；gets(s2)；对于相同的输入Hello World!。s1获取的结果仅仅是Hello，而s2获取的结果则是Hello World!

2、输出

输出一个字符串可以使用printf语句或puts语句。

(1)printf语句

格式：printf(“%s”,字符串名称);

说明：

①用%s格式输出时，printf的输出项只能是字符串(字符数组)名称，而不能是数组元素。

例如：printf(“%s”,a[0]);是错误的。

②输出字符串不包括字符串结束标志符‘\0’。

(2) puts语句

格式：puts(字符串名称);

说明：puts语句输出一个字符串和一个换行符。对于已经声明过的字符串a，printf(“%s\n”,a)和 puts(a)是等价的。

3、字符串处理函数

例2.1.6

数字统计(Noip2010)

【问题描述】

请统计某个给定范围[L, R]的所有整数中，数字2 出现的次数。

比如给定范围[2, 22] ，数字2 在数2 中出现了1 次，在数12 中出现1 次，在数20 中出现1 次，在数21 中出现1 次，在数22 中出现2 次，所以数字2 在该范围内一共出现了6 次。

【输入】

输入文件名为two.in 。

输入共1 行，为两个正整数L 和R，之间用一个空格隔开。

【输出】

输出文件名为two.out 。

输出共1 行，表示数字2 出现的次数。

【输入样例1】two.in

2 22

【输出样例1】two.out

【输入样例2】two.in

2 100

【输出样例2】two.out

【数据范围】

1 ≤L ≤R ≤10000

算法1分析：枚举所有整数，对每一个整数每一位分离处理，判断每一位的数字是否为2。参考代码1：

#include

using namespace std;

main()

{

int i,l,r,x,sum=0;

scanf("%d%d",&l,&r);

for(i=l;i<=r;i++) //枚举所有整数

{

x=i;

while(x>0)

{

if(x%10==2) sum++; //判断个位是否为2，是2累加

x=x/10; //剥离个位，直到为0，结束while循环。

}

printf("%d\n",sum);

return 0;

}

算法2分析：在数据范围内，将每一个整数i转换为字符串s，枚举字符串每一个字符；累加

参考代码2：

#include

using namespace std;

char s[10];

main()

{

int i,l,r,j,sum=0;

scanf("%d%d",&l,&r);

for(i=l;i<=r;i++)

{

sprintf(s,"%d",i);

for(j=0;j

if(s[j]=='2')

sum++;

}

printf("%d\n",sum);

return 0;

}

说明：1.将整数N转化成字符串s，可以用sprintf(s,"%d",N)来实现；2.将字符串s转换成数字N,可以用sscanf(s,"%d",&N)来实现。

例2.1.7简单密码

【问题描述】

Julius Caesar曾经使用过一种很简单的密码。对于明文中的每个字符，将它用它字母表中后5位对应的字符来代替，这样就得到了密文。比如字符A用F来代替。如下是密文和明文

中字符的对应关系。

密文

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

明文

V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

你的任务是对给定的密文进行解密得到明文。

你需要注意的是，密文中出现的字母都是大写字母。密文中也包括非字母的字符，对这些字符不用进行解码。

输入

一行，给出密文，密文不为空，而且其中的字符数不超过200。

输出

输出一行，即密文对应的明文。

样例输入

NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX

样例输出

IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES

分析：观察明文和密文的规律；密文A至E字母,字母的ASCII加21转换为明码；从F到Z，字母的ASCII减5转换为明码。

参考代码：

#include

using namespace std;

char s[201];

int main()

{ gets(s);

for(int i=0;i

if(('A'<=s[i])&&(s[i]<='Z'))

{

if(s[i]+21<=90) printf("%c",s[i]+21);

if(s[i]+21>90) printf("%c",s[i]-5);

}

else

printf("%c",s[i]);

return 0;

}

说明：gets，是从光标开始的地方读到换行符，一整行，包括其中的空格；

Scanf, cin输入内容是从光标开始的地方到空格。

课后练习

训练3 是否为回文字符串

总时间限制: 1000ms

内存限制: 65536kB

描述

给定一个字符串，输出所有长度至少为2的回文子串。回文子串即从左往右输出和从右往左输出结果是一样的字符串，比如：abba，cccdeedccc都是回文字符串。

输入:

一个字符串，由字母或数字组成。长度500以内。

输出:

是回文子字符串，输出”Yes”;不是回文字符串，输出”No”。

样例输入

123321

样例输出

Yes

参考代码：

代码1

#include

using namespace std; char s[5001];

int main()

{

int l,i,j;

bool f=1;

cin>>s;

l=strlen(s);

i=0;

j=l-1;

while(i<=j)

{ if(s[i]==s[j])

{i++;

j--;}

else break;

};

if(i>j) cout<<"Yes";

if(i

return 0;

} 代码2

#include

using namespace std;

char s[5001];

int main()

{

int l,i,j;

bool f=1;

cin>>s;

l=strlen(s);

for(i=0,j=l-1;i<=j;i++,j--) {

if(s[i]!=s[j])

{

f=0;

break;

}

if(f) cout<<"Yes";

else cout<<"No";

return 0;

}

训练4 是否为子串

【问题描述】

输入两个字符串，验证其中一个串是否为另一个串的子串。

输入

输入两个字符串，每个字符串占一行，长度不超过200且不含空格。

输出

若第一个串s1是第二个串s2的子串，则输出(s1) is substring of (s2)

否则，若第二个串s2是第一个串s1的子串，输出(s2) is substring of (s1)

否则，输出 No substring。

样例输入

abc

dddncabca

样例输出

abc is substring of dddncabca

参考代码：

#include

using namespace std;

string a,b;

int main()

{

cin>>a>>b;

if(a.length()

s=a;a=b;b=s;

bool sign=0;

for(int i=0;i

{

int j=0;

for(;j

if(a[i+j]!=b[j]) break;

if(j==b.length())

{

sign=1;

break;

}

if(!sign) puts("No substring");

else cout<

return 0;

}

2.2 顺序查找（刘雪）

知识点

查找是指根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。本节要求熟练掌握顺序查找方法与折半查找方法。

2.2.1 顺序查找

查找是在程序设计中最常用到的算法之一，顺序查找是最基本最简单的查找方式，在查找过程中通常要用到数组来存储数据元素，在扫描数组的过程中又需要用到前面学到的循环知识。

1.基本思想

假定要从n个整数中查找x的值是否存在，最原始的办法是从头到尾逐个查找，这种查找的方法称为顺序查找。

用顺序查找法查找为数组a中值为key的元素，n为要查找的数组元素个数：

int Sequential_Search(int a[], int n, int key)

{

int i;

for(i=1; i <=n; i++)

{

if(a[i] == key)

return i;

}

return 0;

}

优化：有哨兵顺序查找-优化最简单的顺序查找

优化思路：优化部分：a[0]存放要查找的关键字key，减少了数组越界的比较，如果查找表长度很大，还是比最简单的顺序查找快很多的。

int Sequential_Search2(int a[], int n, int key)

{

int i;

a[0] = key;

for(i = n; a[i] != a[0]; i--);

return i;

}

2.平均查找长度（Average Search Length，ASL）

需和指定key进行比较的关键字的个数的期望值，成为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。

Pi：查找表中第i个数据元素的概率。

Ci：找到第i个数据元素时已经比较过的次数。

顺序查找查找成功时的平均查找长度为（假设每个数据元素的概率相等）：ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

当查找不成功时，需要n+1次比较，时间复杂度为O(n)。

3. 典型例题

（1）查找特定的数（Openjudge https://www.wendangku.net/doc/7f12805623.html,/ch0109/01/）

描述：在一个序列（下标从1开始）中查找一个给定的值，输出第一次出现的位置。总时间限制1000ms，内存限制65536kB。

输入：第一行包含一个正整数n，表示序列中元素个数。1 <= n <= 10000。

第二行包含n个整数，依次给出序列的每个元素，相邻两个整数之间用单个空格隔开。元素的绝对值不超过10000。第三行包含一个整数x，为需要查找的特定值。x的绝对值不超过10000。

输出：若序列中存在x，输出x第一次出现的下标；否则输出-1。

样例输入

2 3 6 7 3

样例输出

【分析】：用数组a来存储数据远处，使用循环来扫描数组，直到找到x，输出位置；或者扫描到数组最后，依然没有元素的值等于x，那么说明数组中不存在等于x的值。

【参考程序】：

#include

using namespace std;

int a[10001];

int main(){

int n,x;

cin>>n;

for(int i=1;i<=n;i++){

cin>>a[i];

}

cin>>x;

int b=-1;

for(int i=1;i<=n;i++){

if(a[i]==x){

b=i;

break;

}

cout<

return 0;

}

（2）最高分（Openjudge https://www.wendangku.net/doc/7f12805623.html,/ch0109/02/）

描述：输入学生的人数，然后再输入每位学生的分数和姓名，求获得最高分数的学生的姓名。总时间限制1000ms，内存限制65536kB。

输入：第一行输入一个正整数N（N <= 100），表示学生人数。接着输入N行，每行格式如下：

分数姓名

分数是一个非负整数，且小于等于100；

姓名为一个连续的字符串，中间没有空格，长度不超过20。

数据保证最高分只有一位同学。

输出：获得最高分数同学的姓名。

样例输入

87 lilei

99 hanmeimei

97 lily

96 lucy

77 jim

样例输出

hanmeimei

【分析】：顺序查找最高分，定义score和name两个数组，分别来存储学生的分数和姓名。用变量high来记录最高分，初值设为0，在输入分数的同时跟high进行比较，如果输入的分数大于high，则将分数记录到high，并用变量k记录最高分的位置，最后输出name[k]。【参考程序】：

#include

using namespace std;

int score[101]; //学生分数

string name[101]; //学生姓名

int main(){

int n;

cin>>n;

int high=0,k; //high记录最高分，k保存最高分的位置

for(int i=0;i

cin>>score[i]>>name[i];

if(score[i]>high){

high=score[i];

k=i;

}

cout<

return 0;

}

（3）不高兴的津津（来源：NOIP2004复赛普及组第一题https://www.wendangku.net/doc/7f12805623.html,/ch0109/03/）描述：津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。

输入：包括七行数据，分别表示周一到周日的日程安排。每行包括两个小于10的非负

整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。

输出：包括一行，这一行只包含一个数字。如果不会不高兴则输出0，如果会则输出最不高兴的是周几（用1, 2, 3, 4, 5, 6, 7分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。

样例输入

5 3

6 2

7 2

5 3

5 4

0 4

0 6

样例输出

【分析】：用数组a和b分别表示学校上课时间和复习班上课时间，用数组c记录两者之和。定义bool类型的变量p来判断一天的上课时间是否超过8小时，初值为true表示未超过8小时，一旦超过8小时，拍的值变为false。用m来记录一天上课最多的时间，m初值为8，通过比较寻找最大值，用k来记录最大值的位置。

【参考程序】：

#include

using namespace std;

int a[10],b[10],c[10];

int main(){

int m=8,k;

bool p=true;

for(int i=1;i<7;i++){

cin>>a[i]>>b[i];

c[i]=a[i]+b[i];

if(c[i]>8) p=false;

if(c[i]>m){

m=c[i];

k=i;

}

if(p) cout<<0;

else cout<

}

4. 课后训练

训练1. 最大值和最小值之差

描述：输出一个整数序列中最大的数和最小的数的差。总时间限制:1000ms；内存限制: 65536kB。

输入：第一行为M，表示整数个数，整数个数不会大于10000；第二行为M个整数，以空格隔开，每个整数的绝对值不会大于10000。

输出：输出M个数中最大值和最小值的差。

样例输入

2 5 7 4 2

样例输出

【参考程序】：

#include

using namespace std;

int a[10001];

int main(){

int m,max=-10001,min=10001;

cin>>m;

for(int i=0;i

{

cin>>a[i];

}

for(int i=0;i

if(a[i]>max) max=a[i];

if(a[i]

}

int diff=max-min;

cout<

return 0;

}

训练2. 笨小猴（来源NOIP2008复赛提高组第一题https://www.wendangku.net/doc/7f12805623.html,/ch0109/06/）描述：笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！

这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn 是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。

输入：只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。

输出：共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”；

第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。

样例输入

样例#1：

error

样例#2：

olympic

样例输出

样例#1：

第2部分 语言提高班

第2部分语言提高班