【C/PTA】数组进阶练习（三）

本文结合PTA专项练习带领读者掌握数组，刷题为主注释为辅，在代码中理解思路，其它不做过多叙述。

7-1 数组-排名查询

已知N个人的成绩排名，按排名从小到大输出这N个人的编号。
输入格式:

第一行输入一个正整数N(N<=100)；

第二行输入N个互不相同的整数，每个整数均取值为1到N。
输出格式:

输出仅一行，包括N个整数，其中第i个整数表示排第i名的人的编号。

数字之间用一个空格隔开，最后一个数字之后没有空格。
输入样例:

5
2 3 1 5 4

输出样例:

3 1 2 5 4

#include 
int main()
{
	int n;scanf("%d",&n);
	int a[n];
	
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}//输入23154
	
	
	int count=0;
	for(int i=1;i<=n;++i) //假设第一次循环i=1
	{
		for(int j=0;j<n;++j)
		{
			if(a[j]==i)   //j=2时a[j]=1 
			{
				if(count==n-1) //对最后一个数字进行处理
				{
					printf("%d",j+1);
				}
				else 
				printf("%d ",j+1); //输出编号3
				count++;
				break;
			}
		}
	}
	
}
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

7-2 数组-人数过半

输入N个数，求出现次数超过总数一半的数。数据保证存在这个数。
输入格式:

第一行输入一个正整数N(N<1000)；

第二行输入N个数，每个数的绝对值不超过1e9。
输出格式:

输出一个数，即出现次数超过总数一半的数。
输入样例:

5
2 3 2 2 4

输出样例:

2

#include 
int main()
{
	long long int n;scanf("%lld",&n);long long int a[n];
	for(long long int i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);	
	}
	
	for(long long int i=0;i<n-1;i++)
	{
		for(long long int j=0;j<n-i-1;j++)
		{
		if(a[j]>a[j+1])
		{
			long long int t=a[j+1];
			a[j+1]=a[j];
			a[j]=t;
		    }	
		}
	}
	
	//进行最大数的判断
	long long int count=1;
	for(long long int i=0;i<n-1;i++)
	{
		if(a[i]==a[i+1])
		count++;
		else
		count=1;
		
		if(count>n/2)
		{
		printf("%lld",a[i]);
		break;
		}	
	}
}
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

7-3 数组-数值插入

输入一个非降序列和一个数，将这个数插入到非降序列中并保持序列非降。
输入格式:
第一行输入一个正整数N(N<100000)；
第二行按顺序输入N个非降的整数，保证每个整数在int范围；
第三行输入一个待插入的整数（int范围）。

输出格式:
输出仅一行，包括N+1个整数，为插入给定的数后的非降序列，数字之间用一个空格隔开，最后一个数字之后没有空格。

输入样例:
5
3 5 7 10 15
8

输出样例:
3 5 7 8 10 15

//将一个数插入到非降序列中并保持序列非降
#include 
int main()
{
	int n;scanf("%d",&n);int a[n+1];
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	int x;
	scanf("%d",&x);
	
	for(int i=0;i<n;i++)
	{
	//x最小的情况
	if(x<=a[0])
	{//逆序往后移
		for(int j=n-1;j>=0;j--)
		{
			a[j+1]=a[j];
		}
		//x赋值给a[0]
		a[0]=x;
		break;
	}
	
	//x在其中的情况
	else if(x>=a[i]&&x<=a[i+1])
	 {
		//逆序往后移
		for(int j=n-1;j>=i+1;j--)
		{
			a[j+1]=a[j];
		}
		//把x赋值给a[i+1]
		a[i+1]=x;
		break;
	 } 
	 
	 
	 //x最大的情况
	 else if(x>=a[n-1])
	 {
	 	a[n]=x;
	 }

	}
	
	for(int i=0;i<=n;i++)
	{
		if(i==n)
		printf("%d",a[i]);
		else
		printf("%d ",a[i]);
	}
}
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

7-4 数组-冒泡排序

给定n个整数，请用冒泡排序法对这n个整数从小到大排序。
输入格式:

第一行输入一个正整数N(N<=1000)；

第二行输入N个整数（int范围）。
输出格式:

输出仅一行，为排完序后的N个数，两个数之间用一个空格隔开。
输入样例:

5
3 5 4 3 5

输出样例:

3 3 4 5 5

#include 
int main()
{
	int n;scanf("%d",&n);int a[n];
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-i-1;j++)
		{
			if(a[j]>a[j+1])
			{
				int t=a[j+1];
				a[j+1]=a[j];
				a[j]=t;
			}
		}
	}
	

	for(int i=0;i<n;i++)
	{
		if(i==n-1)
		printf("%d",a[i]);
		else
		printf("%d ",a[i]);
	}
}
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

7-5 数组-删除元素

输入一个序列和一个数，将这个序列中与该个数相等的元素删除，保持其他元素先后顺序不变。
输入格式:

第一行输入n(2

第二行输入n个正整数（小于1e9）；

第三行输入一个正整数k，为要删除的元素值。
输出格式:

输出仅一行，即进行删除后的序列，两个元素之间有一个空格作为分隔符，末尾无空格。
输入样例:

4
3 5 3 2
3

输出样例:

5 2

方法一：特殊值法

#include 
int main()
{
	int n;scanf("%d",&n);int a[n];
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	int x;
	scanf("%d",&x);
	
	for(int i=0;i<n;i++)
	{
		if(x==a[i])
		{
			a[i]=1999999;//取特殊值
		}
	}
	
	
	
	for(int i=0;i<n;i++)
	{
		if(a[i]!=1999999)
		{
			if(i==n-1||a[i+1]==1999999)
			printf("%d",a[i]);
		    else
			printf("%d ",a[i]);
		}
	
   }
}
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

方法二：使用双指针来实现。一个指针用于遍历原数组，另一个指针用于记录删除指定元素后的新数组的位置。

#include 
int main(){
    int n;scanf("%d",&n);int a[n];
    
	for(int i=0;i<n;i++) 
	{
        scanf("%d",&a[i]);
    }

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

    int k=0;//用于记录新数组

    for(int i=0;i<n;i++) 
	{
        if(a[i]!=x) 
		{
            a[k]=a[i];//将非指定元素移到前面
            k++;
        }
    }

    for (int i=0;i<k;i++) 
	{
		if(i==k-1)
		printf("%d",a[i]);
        else
		printf("%d ", a[i]);
    }
}
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

7-6 数组-歌手得分

青年歌手大奖赛中，评委会给参赛选手打分。选手得分规则为：去掉一个最高分和一个最低分，然后计算出平均分即为选手最终得分。
输入格式:

第一行输入一个正整数n(2

第二行输入n个整数，表示n个评委的打分。
输出格式:

输出仅一行，即选手的最终得分，结果保留2位小数。
输入样例:

4
100 99 98 97

输出样例:

98.50

#include //使用冒泡排序即可
int main()
{
	int n;scanf("%d",&n);int a[n];double sum;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}


	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-i-1;j++)
		{
			if(a[j]>a[j+1])
			{
				int t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
			}
		}
	}
	
	for(int i=1;i<=n-2;i++)
	{
		sum+=a[i];
	}
	double aver=sum/(n-2);
	printf("%.2f",aver);
}
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

7-7 数组-前K个成绩

已知N个人的成绩，编号从1到N，输出成绩排名前K个人的成绩。
输入格式:

第一行输入一个正整数N(N<=100)；

第二行输入N个正整数（范围为1到100），即学生的成绩；

第三行输入一个正整数K（K>=1）。
输出格式:

输出仅一行，即前K个人的成绩。成绩从高到低输出。每两个数据之间有一个空格，末尾没有空格。
输入样例:

5
10 20 30 40 50
2

输出样例:

50 40

#include //冒泡排序即可
int main()
{
	int n;scanf("%d",&n);int a[n];
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	int k;scanf("%d",&k);


	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-i-1;j++)
		{
			if(a[j]<a[j+1])
			{
				int t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
			}
		}
	}
	
	for(int i=0;i<k;i++)
	{
		if(i==k-1)
			printf("%d",a[i]);
		else
		printf("%d ",a[i]);
	}
}
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

7-8 数组-绝对值排序

输入n(n<=100)个整数，按照绝对值从大到小排序后输出。绝对值相同的两个数，原始值较小的那个数靠前。
输入格式:

第一行输入一个整数n(1<=n<=100)；

第二行输入n个待排序的整数（int 范围）。
输出格式:

输出排序后的结果，两个数之间用一个空格隔开，末尾没有空格。
输入样例:

3
3 -4 2

输出样例:

-4 3 2

#include 
int main()
{
	int n;scanf("%d",&n);int a[n],b[n];
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i];//用数组b来跟踪数组a的状态
		if(a[i]<0)
		{
			a[i]*=-1;
		}
		
	}


	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-i-1;j++)
		{
			if(a[j]<a[j+1])
			{
				int t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;  //冒泡排序
				
				int s=b[j];
				b[j]=b[j+1];
				b[j+1]=s;
			}
			
			if(a[j]==a[j+1])//处理绝对值相同的两个数
			{
				if(b[j]>b[j+1])
				{
					int q=b[j+1];
					b[j+1]=b[j];
					b[j]=q;
				}
			}
		}
	}
	
	for(int i=0;i<n;i++)
	{
		if(i==n-1)
		{
			if(b[i]<0)
			printf("%d",b[i]);
			else
			printf("%d",a[i]);
		}
			
		else
		{
			if(b[i]<0)
			printf("%d ",b[i]);
			else
			printf("%d ",a[i]);
		}
		
	}
}
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

7-9 数组-该死的数学课

为了提高菇菇们的基本素质来抵抗清明SAMA的恐怖袭击，麻麻决定给菇菇们上数学课（数学课有什么用啊喂！(#`O′) ？！）。麻麻给了菇菇们N个从2 开始的连续偶数，要求它们每M个整数计算出平均值，并输出。菇菇们太难过了，该死的数学课总是让人想哭，你能帮帮它们么？
输入格式:

输入仅一行，包括两个整数N(<=100)和M。
输出格式:

输出每M个连续偶数的平均值，末尾不足M个按实际个数计算输出。
输入样例:

3 2

输出样例:

3 6

#include 
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	int a[n];a[0]=2;
	for(int i=1;i<n;i++)
	{
		a[i]=a[i-1]+2;
	}
	
	int groupcount=n/m;
	int remain=n%m;
	int sum,aver;
	int j=0,end=m,i;
	
	for(int k=1;k<=groupcount;k++)
	{//对每组进行处理
		sum=0;
		for(i=j;i<end;i++)
		{
			sum+=a[i];	
		}
		aver=sum/m;
		
		if(i==n)//对不存在余数时末尾空格的处理
		printf("%d",aver);
		else
		printf("%d ",aver);
		
		
		j+=m;
		end+=m;
	//每组处理完后 区间向右移m个单位
	}
	
	if(remain>0)
	{//处理剩余个数
		int all=0;
		for(int i=groupcount*m;i<n;i++)
		{
			all+=a[i];
		}
		int x=all/(n-groupcount*m);
		printf("%d",x);
	}

}
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

7-10 数组-麻麻的起司猫

广袤的戈壁上，为首的菇菇麻麻养了一群以节操为食的起司猫（都没节操喂菇菇了啊喂！还养猫？！）。麻麻每次考虑它们的DM值喂给它们节操。为了让起司猫们不要吃太饱，麻麻决定每次喂给DM值最低的起司猫ai块节操。吃下节操的起司猫DM值将相应地增加ai。

输入格式:
第一行输入两个正整数N，M（0 第二行包括N个整数，表示每只起司猫最初的DM值；
第三行包括M个整数，表示每次喂食的节操ai。

输出格式:
输出仅一行，表示M次喂食过后DM值最低的起司猫的DM值（保证数据不超过10^9）。

输入样例:
3 1
1 2 3
3

输出样例:
2

#include 
int main()
{
	int n,m;scanf("%d%d",&n,&m);int a[n],b[m];
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	for(int i=0;i<m;i++)
	{
		scanf("%d",&b[i]);
	}
	
	
	for(int i=0;i<m;i++)
	{
		//次数作为外层循环
		int less=0;
		for(int j=1;j<n;j++)
		{
			if(a[j]<a[less])
			{
				less=j;   
			}

		}
		a[less]+=b[i];//喂食给最小的猫    
	}
	
	
    int min=a[0];
	for(int i=0;i<n;i++)
	{
		if(min>a[i])
		min=a[i];
	}
	printf("%d",min);
}
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

7-11 数组-小光头的反攻

小姑凉自从找到了一直拥有蓝爸爸的方法后就再也不需要小光头了，小光头觉得很难过。于是小光头偷偷跟着小姑凉一起去上数学课，想知道小姑凉怎么变得这么厉害（跟数学课真的有关系么？= =）。他发现从小就只会玩火的小姑凉数学真的糟透了，于是他想出了一个办法，他和小姑凉打赌，如果小姑凉不能解出他给的题目，小姑凉就要把蓝爸爸让给他，还不能生气，要跟他一起愉快地玩耍。小姑凉涉世未深，于是天真地答应了。

小光头的题目是这样的：小光头家有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

当然，从小就只玩火的小姑凉一定是解不出来的啦，你能帮帮她么？
输入格式:

第一行包含一个整数N，表示共有N组数据；

接下来有N行，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。
输出格式:

对于每组数据中的楼梯级数，输出不同走法的数量。
输入样例:

3
1
2
3

输出样例:

1
1
2

#include 
int main()
{
    int n;scanf("%d",&n);
	while(n--)
	{
		int m;scanf("%d",&m);
		int a[50];
		
		a[1]=1;//到达第一阶的走法为1
		a[2]=1;//...为2
		
		for(int i=3;i<=m;i++)
		{
			a[i]=a[i-1]+a[i-2];
		}
		printf("%d",a[m]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

7-12 数组-无聊的游戏

Alice和Bob 整天都喜欢玩无聊的游戏，今天他们玩的游戏的规则是两人轮流从自己的 牌堆的最上方取一张牌，牌上有一个数字，谁的数字大谁就获胜，数字相同时两人都不 算获胜，问最后谁获胜的次数多。输出获胜次数多的人的名字及获胜的次数。获胜次 数相同时算Bob获胜。
输入格式:

第一行为一个正整数N（0 < N <= 1000），表示每个人有N张牌。

第二行包含N个数字，为Alice的牌的大小。

第三行包含N个数字，为Bob牌的大小。

（牌的大小为正整数且不超过1000，输入数字的顺序就是牌堆的牌从上到下的顺序）。
输出格式:

输出有两行，第一行为获胜者的名字；

第二行为获胜的次数。
输入样例1:

5
1 2 4 4 5
5 4 3 2 1

输出样例1:

Alice
3

输入样例2:

5
1 2 3 4 5
5 4 3 2 1

输出样例2:

Bob
2

#include 
int main()
{
	int n;scanf("%d",&n);
	int a[n],b[n];
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;i++)
	{
		scanf("%d",&b[i]);
	}
	
	
	int alice=0,bob=0;
	for(int i=0;i<n;i++)
	{
		if(a[i]>b[i])
		alice++;
		else if(a[i]<b[i])
		bob++;
	}
	
	if(alice>bob)
	printf("Alice\n%d",alice);
	else if(alice==bob)
	printf("Bob\n%d",bob);
	else
	printf("Bob\n%d",bob);
}
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

7-13 数组-Shc的数字

Shc 有一堆数字。这些数字十分的乱，有正有负。Shc 现在想从这些数字中挑选出一段连续的数字去送给他最喜欢的MAZE。Shc 知道MAZE 喜欢数字越大越好。所以他希望能够选出数字和最大的一段数字送给MAZE。现在需要你算出这段序列的和是多少。

输入格式:
第一行为一个正整数N（0 < N <= 100000），表示有N个数；
第二行输入N个数 Ai (-1000 <= Ai<= 1000)。

输出格式:
输出仅一个整数，表示最大的一段数字和值。

输入样例:
5
-1 2 -3 4 5

输出样例:
9

#include 
int main()
{
	int n;scanf("%d",&n);int x,nowall=0,max=-9999;//nowall表示当前序列和
	for(int i=0;i<n;i++)
	{
		scanf("%d",&x);
		if(x>nowall+x)
		{
			nowall=x;//如果x 大于 包含x的序列和,则说明nowall为负数
			//此时把序列更新
		}
		else
		nowall+=x;
		
		if(nowall>max)
		max=nowall;
	}
	
	printf("%d",max);
}
//拿2、-3、4、5举例
//一开始nowall为0，所以nowall加2，变为2，因为max为-9999，所以max变为2
//输入-3，同理，nowall变为-1，nowall不会大于max，所以max仍为2
//输入4，4+nowall大于nowall，所以nowall被更新为4，也就是说现在从4开始计算序列
//4大于max，所以max变为4
//输入5，所以nowall+5变成9，9大于max，所以序列和为9
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

7-14 数组-简单的斐波那契数列

斐波那契数列是一种非常有意思的数列，由0和1开始，之后的斐波那契系数就由之前的两数相加。用数学公式定义长度为n斐波那契数列F则可以看成如下形式：

F_0=0;

F_1=1;

F_i=F_{i-1}+F_{i-2}(2<=i

由于斐波那契数列的增长速度很快，我们在斐波那契数列上进行取模操作，得到对应的长度为n的F’数列：

F_0’=0;

F_1’=1;

F_i’=(F_{i-1}’+F_{i-2}’)%1000000007(2<=i

现在给你一个数列，你需要判断它是否为F’数列。

输入格式:
第一行包含一个正整数n（1<=n<=1000),表示有n个数；
第二行包含n个非负整数，均在int范围内。

输出格式:
输出仅一行，如果输入的数列是长度为n的F’数列则输出“YES”，否则输出“NO”。

输入样例1:
4
0 1 1 3

输出样例1:
NO

输入样例2:
8
0 1 1 2 3 5 8 13

输出样例2:
YES

#include 
int is(int n,int a[])
{
	if(n==1)
	{
		if(a[0]==0)
		return 1;//仅有0 则是F'数列
		else
		return 0;
	}
	
	
	int b1=0,b2=1,c;
	for(int i=2;i<n;i++)
	{
		c=(b1+b2)%1000000007;
		if(a[i]!=c)
		return 0;//如果有一个数不相等，则肯定不是F'数列
		b1=b2;
		b2=c;
	}//如果循环能正常结束，则是F'数列
	return 1;
}

int main()
{
	int n;scanf("%d",&n);int a[n];
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	if(is(n,a))
	printf("YES");
	else
	printf("NO");
	
}
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

7-15 数组-简单的游戏

HHD学长很强，他玩VAN游戏总是赢。

这天他拿出N张牌，想和你玩个游戏，游戏的规则如下：
每张牌的点数为Ai（1<=i<=N),两人从牌堆顶轮流取牌，为了表示尊重，由学长先手取牌，最后点数之和大的获胜。

学长是个好面子的人，如果他输了，他会很不开心。你是个懂事的学弟，为了尽可能让学长赢，你可以趁学长不注意，在某一轮取牌结束后丢掉这张牌。如果丢掉这张牌后，学长还是要输，则输出“RUN”；否则输出你要丢掉的是第几轮取到的牌，使得学长的点数和尽可能大过你。
输入格式:

第一行输入一个正整数N（2 <= N <= 1000），表示有N张牌；

第二行输入N个整数，为牌的点数（牌的点数均为正整数且不超过1000，输入数字的顺序就是牌堆的牌从上到下的顺序）。
输出格式:

输出仅一行，输出一个整数，表示你要丢掉第几次取的牌才能让学长赢得漂亮；否则输出“RUN”。
输入样例1:

5
1 2 4 4 5

输出样例1:

2

输入样例2:

6
1 2 1 4 1 6

输出样例2:

RUN

#include 
int main()
{
	int n;scanf("%d",&n);int x;
	
	int maxmy=0;//你当前摸到的最大的牌
	int maxmycount=1;//你要丢牌的轮数
	int allmy=0;//你的点数和
	int allhe=0;//他的点数和
	
	
	
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if(i%2==1)
		allhe+=x;//1 2 3
		else
		{
			if(x>maxmy)//如果你摸到的牌比你之前的都大
			{
				maxmy=x;
				maxmycount=i/2;
			}
			allmy+=x;
		}
	}
	
	if(allmy-maxmy<allhe)
	printf("%d",maxmycount);
	else
	printf("RUN");
		
}
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

7-16 数组-买买买

一次，HHD学长路过一个地摊，发现地摊上陈列着一排算法书，从1-N编号（1<=N<=1000000）。每本书价格为Ai（1<=Ai<=100)。于是他想考考你，当他给出一个区间[L,R]，你要立即回答出这个区间内书的价格总和，如果你答对了，他就买下这些书。我们的HHD学长还真是富有啊！
输入格式:

第一行输入两个正整数N，Q（0 < N <= 1000000)，N表示书的数量，Q表示询问的次数（0

第二行包括N个整数，表示N本书的价格；

接下来Q行，每行两个整数L、R，表示区间（1<=L<=R<=N)。
输出格式:

输出共Q行，每行对应一次询问的答案。
输入样例:

8 3
5 4 7 2 5 8 7 7
1 3
8 8
4 5

输出样例:

16
7
7

#include 
int main()
{
	int n,q;
	scanf("%d%d",&n,&q);int a[n];
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	int l,r;
	for(int i=0;i<q;i++)
	{
		int sum=0;
		scanf("%d%d",&l,&r);
		for(int i=l-1;i<r;i++)
		{
			sum+=a[i];
		}
		printf("%d\n",sum);
	}
	
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

7-17 数组-牌面累加

粉红猪和呲溜喵在玩游戏，规则如下：每个人有N张牌，每张牌有一个数字，从第一张牌开始累加，累加和大的获胜。
输入格式:

第一行包含一个正整数N（0 < N <= 1000），表示有N张牌；

第二行包含N个整数，为呲溜喵的牌的大小；

第三行包含N个整数，为粉红猪牌的大小；

牌的大小可正可负，输入数字的顺序就是牌堆的牌从1到N的顺序。
输出格式:

输出仅一行，为获胜者的名字（pig或者cat）；若平局则输出“sad”（不包含引号）。
输入样例1:

5
1 2 4 3 5
5 4 3 2 1

输出样例1:

sad

输入样例2:

5
1 2 3 4 5
5 -1 -1 -1 -1

输出样例2:

cat

#include 
int main()
{
	int n;scanf("%d",&n);int a[n];
	int sum=0,all=0;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		all+=a[i];
	}
	if(all>sum)
	printf("pig");
	else if(all==sum)
	printf("sad");
	else
	printf("cat");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

7-18 数组-咸鱼翻身

粉红猪比较无聊，他会每次改变当前所有咸鱼的状态（正面翻成反面，反面翻成正面），经过m次操作后，n条咸鱼中有几条是正面朝上的呢？
输入格式:

第一行输入两个正整数n，m（1<=n<=1000,0<=m<=1000）。n代表咸鱼数量，m代表操作次数。

第二行包含n个整数（0或1），表示咸鱼的初始状态，其中0代表反面，1代表正面。
输出格式:

输出仅一个整数，表示经过m次操作后，正面朝上的咸鱼数。
输入样例:

3 3
1 0 1

输出样例:

1

#include 
int main()
{
	int n,m;scanf("%d%d",&n,&m);int a[n];
	int count=0;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]==1)
		count++;
	}
	
	if(m%2==0)//经过偶数次操作就相等于什么都没做
	printf("%d",count);
	else
	printf("%d",n-count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

7-19 数组-冰欺凌球

呲溜喵很喜欢吃冰淇凌，特别喜欢夹冰淇凌球，现在给出呲溜喵已经加的冰淇凌球的半径，你能从大到小输出每颗冰淇凌球的体积吗？
输入格式:

第一行输入一个正整数N（0 < N <= 1000），表示有N个冰淇凌球；

接下来N行每行输入一个半径r(r 为1到100的任意实数)。
输出格式:

输出共N行，每行一个数字，表示一个冰淇凌的体积（体积保留两位小数，且按照从大到小的顺序）。

Pi = acos（-1.0）
输入样例:

3
1.2
2.4
3.1

输出样例:

124.79
57.91
7.24

#include 
#include 
int main()
{
	int n;scanf("%d",&n);double a[n];
	for(int i=0;i<n;i++)
	{
		scanf("%lf",&a[i]);
		a[i]=acos(-1.0)*4/3*a[i]*a[i]*a[i];
	}


//冒泡排序
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-i-1;j++)
		{
			if(a[j]<a[j+1])
			{
				double t=a[j];
				a[j]=a[j+1];
				a[j+1]=t;
			}
		}
	}
	
	for(int i=0;i<n;i++)
	{
		printf("%.2f\n",a[i]);
	}

}
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

7-20 数组-粉红猪的斐波那契数列

粉红猪很喜欢斐波那契数列，现在希望你给出第n项的结果。
输入格式:

输入仅一行，包含一个正整数n（1<=n<=55）。
输出格式:

输出仅一个整数，表示斐波那契数列第n项的值。
输入样例:

3

输出样例:

2

#include 
int main()
{
	int n;
	scanf("%d",&n);
	
	long long int a=1,b=1;
	if(n==1)
	printf("%lld",a);
	else if(n==2)
	printf("%lld",b);
	else
	{
     	long long int c;
	    for(int i=3;i<=n;i++)
    	{
		c=a+b;
		a=b;
		b=c;
    	}
    	printf("%lld",c);
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

7-21 序列元素删除

粉红猪不喜欢一些数字，所以他不希望这些数字出现在序列中。现在请你来帮粉红猪删除这些数字。
输入格式:

输入一共四行。

第一行输入一个正整数N（1<=N<=1000）；

接下来一行包括N个整数；

第三行一个正整数M（0<=M<=100），代表粉红猪不喜欢的数的个数；

接下来一行包括M个数，代表粉红猪不喜欢的数（保证互不相同）。
输出格式:

输出处理后的序列，其他元素位置不变（行末无空格，仅有回车）；如果删除后没有元素存在，只输出行末的回车。
输入样例:

6
1 2 5 3 4 5
1
5

输出样例:

1 2 5 3 4

#include 
int main()
{
	int n;scanf("%d",&n);int a[n];//原序列
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);
	
	int m;scanf("%d",&m);int b[m];//不喜欢的数组成的序列
	for(int i=0;i<m;i++)
	scanf("%d",&b[i]);
	
	

	
	for(int i=n-1;i>=0;i--)
	{//从原序列的最后开始遍历
		for(int j=0;j<m;j++)
		{
			if(a[i]==b[j])
			{
				for(int k=i;k<n-1;k++)
				{
				a[k]=a[k+1];//把后面的值赋给当前的数
				}
				n--;	
				break;
			}
		}

	}
	
	if(n==0)
	{
		printf("\n");
	}
	else if(n==1)
	{
		printf("%d\n",a[0]);
	}
	else
	{
			for(int i=0;i<n-1;i++)
			printf("%d ",a[i]);
			printf("%d\n",a[n-1]);
	}
}
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

7-22 数组-田地之争

转眼间双十一又来了，又到了戈壁上菇菇一族分配土地的日子（什么奇葩设定啊！）。为了公平起见，麻麻想出了一个聪明的办法：将土地分为N块，菇菇们一起到每块土地区域接受任务，最后完成任务最多的菇菇有优先选择权。因为可能在一个区域上重复接受任务，菇菇们记混了任务属于哪个区域，你能帮忙它们抢到选择权么？
输入格式:

第一行输入一个整数N（<=100），表示共有N个区域。

接下来有多行，每行两个整数a和b，表示在a区域接受了b个任务（同一个区域可能接受多次），当a、b同为0时结束输入。
输出格式:

输出共N行，每行包含两个整数a和b，a为区域编号，b表示a区域共接受了多少任务。（要求按区域编号从小到大排序,区域编号不大于100）
输入样例:

3
1 3
2 3
3 4
1 7
0 0

输出样例:

1 10
2 3
3 4

#include 
int main()
{
	int n;scanf("%d",&n);
	int task[100]={0};

    int a,b;
	while(1)
	{
		scanf("%d%d",&a,&b);
		if(a==0&&b==0)
		break;
		task[a-1]+=b;
	}
	
	for(int i=0;i<n;i++)
	{
		printf("%d %d\n",i+1,task[i]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

7-34 数组-转置矩阵

给定一个n*m的矩阵，请你帮忙求出这个矩阵的转置矩阵。
输入格式:

第一行包含两个正整数n，m（0 < n，m <= 1000）。

接下来有n行，每行包含m个正整数，每两个数之间用一个空格隔开。所有的正整数均满足小于等于1000。
输出格式:

输出共m行，每行有n个正整数，每两个数之间用一个空格隔开，行末没有空格。即原矩阵的转置矩阵。
输入样例:

3 2
1 2
3 4
4 5

输出样例:

1 3 4
2 4 5

#include 
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	int a[1000][1000];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}


	for(int j=0;j<m;j++)
	{
		for(int i=0;i<n;i++)
		{
			printf("%d",a[i][j]);
			if(i!=n-1)
			printf(" ");
		}
		printf("\n");
	}
	
}
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

7-37 数组-病人排序

医院每天会有很多病人，现在给出病人的编号（编号可能相同）和生病的严重程度（数值越大越严重），希望你将病人排序后输出（生病严重程度从大到小，相同程度的编号小的在前）。
输入格式:

第一行输入一个正整数N（1<=N<=10^3）；

接下来N行，每行两个整数id，priority，分别代表病人编号和生病严重程度。
输出格式:

输出共N行，每行一个整数，即按要求排好序的病人的编号。
输入样例:

2
1 100
2 10000

输出样例:

2
1

#include 
int main()
{
	int n;scanf("%d",&n);int a[n],b[n];
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
	}
	
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-i-1;j++)
		{
			if((b[j]<b[j+1])||(b[j]==b[j+1]&&a[j]>a[j+1]))//  <保证了输出时编号小的在前
			{
				int t=b[j];
				b[j]=b[j+1];
				b[j+1]=t;//当对程度进行冒泡排序时
				
				int s=a[j];//编号也需要排序
				a[j]=a[j+1];
				a[j+1]=s;
			}
		}
	}
	
	for(int i=0;i<n;i++)
	{
		printf("%d\n",a[i]);
	}
}
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

7-43 数组-帮AC怪找子串

AC monster对Accept情有独钟。

现在希望你能找出输入的字符串中所含“Accept”的个数。

例如：WEQAcceptopiacceptwAcceptqqq中含有2个“Accept”子串。
输入格式:

输入仅一行，包含一个长度不超过10000个字符的字符串。
输出格式:

输出一个整数，表示“Accept”子串的个数。
输入样例1:

aeqweqsssaccept

输出样例1:

0

输入样例2:

Acceptiiiioac

输出样例2:

1

#include 
#include 
int main()
{
	char a[10001];
	scanf("%s",a);
	int len=strlen(a);
	int count=0;
	for(int i=0;i<=len;i++)
	{
		int found=1;
		for(int j=0;j<6;j++)
		{
			if(a[i+j]!="Accept"[j])//"Accept"[j]表示字符串常量"Accept"中的第j个字符
			//由j递增来检查i到i+6是否与accept相同
			{
				found=0;
				break;
			}
		}
	if(found)
	count++;
	}
	printf("%d\n",count);	
}
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

7-44 数组-LEN7回文串

呲溜喵很喜欢7这个数字，请你找出输入字符串中，长度为7的所有回文串。
输入格式:

输入仅一行，包括一个长度不超过1000的字符串。
输出格式:

分多行输出原字符串中所有长度为7的回文子串，每行输出一个，行末均有回车（数据保证有解）。
输入样例:

abababacacadddac

输出样例:

abababa
cadddac

#include 
#include 

int is(char *a,int start,int end)
{
	while(start<end)
	{
		if(a[start]!=a[end])
		return 0;
		start++;end--;
	}
	return 1;
}

int main()
{
	char a[1001];
	scanf("%s",a);
	int len=strlen(a);
	
	for(int i=0;i<=len;i++)//区间开头以1递增，间隔为6开始遍历
	{
		if(is(a,i,i+6))//先判断是否为回文数列
		{
			for(int j=i;j<i+7;j++)
			printf("%c",a[j]);
			printf("\n");
		}
		
	}
}
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

7-45 字符串逆序

输入一个字符串，对该字符串进行逆序，输出逆序后的字符串。
输入格式：

输入在一行中给出一个不超过80个字符长度的、以回车结束的非空字符串。
输出格式：

在一行中输出逆序后的字符串。
输入样例：

Hello World!

输出样例：

!dlroW olleH

方法一：数组实现

#include 
int main()
{
	char c,a[80];
	int i=0;
	while((c=getchar())!='\n')
	{
		a[i]=c;
		i++;
	}
	
	for(int j=i-1;j>=0;j--)
	{
		printf("%c",a[j]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法二：引入gets及strlen

#include 
#include 
int main()
{
	char a[80];
	gets(a);
	
	for(int i=strlen(a)-1;i>=0;i--)
	printf("%c",a[i]);
	
}
1
2
3
4
5
6
7
8
9
10
11

7-46 字符串替换

本题要求编写程序，将给定字符串中的大写英文字母按以下对应规则替换：

原字母 	对应字母
A 	Z
B 	Y
C 	X
D 	W
… 	…
X 	C
Y 	B
Z 	A
1
2
3
4
5
6
7
8
9

输入格式：

输入在一行中给出一个不超过80个字符、并以回车结束的字符串。
输出格式：

输出在一行中给出替换完成后的字符串。
输入样例：

Only the 11 CAPItaL LeTtERS are replaced.

输出样例：

Lnly the 11 XZKRtaO OeGtVIH are replaced.

#include 
int main()
{
	char c,a[80],b[80];
	int i=0;
	while((c=getchar())!='\n')
	{
		a[i]=c;
		i++;
	}
	
	for(int j=0;j<=i-1;j++)
	{
		if(a[j]>='A'&&a[j]<='Z')
		{
			b[j]='A'+'Z'-a[j];
		}
		else 
		b[j]=a[j];
		
		printf("%c",b[j]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

7-47 统计字符出现次数

本题要求编写程序，统计并输出某给定字符在给定字符串中出现的次数。
输入格式：

输入第一行给出一个以回车结束的字符串（少于80个字符）；第二行输入一个字符。
输出格式：

在一行中输出给定字符在给定字符串中出现的次数。
输入样例：

programming is More fun!
m

输出样例：

2

方法一：数组实现

#include 
int main()
{
	char a[80],c,d;
	int i=0,count=0;
	while((c=getchar())!='\n')
	{
		a[i]=c;
		i++;
	}
	d=getchar();
	
	for(int j=i-1;j>=0;j--)
	{
		if(d==a[j])
		count++;
	}
	printf("%d",count);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法二：引入gets及strlen

#include 
#include 
int main()
{
	char a[80],c;
	int count=0;
	
	gets(a);
	c=getchar();
	
	for(int i=0;i<strlen(a);i++)
	{
		if(a[i]==c)
		{
			count++;
		}
	}
	printf("%d",count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

7-48 IP地址转换

一个IP地址是用四个字节（每个字节8个位）的二进制码组成。请将32位二进制码表示的IP地址转换为十进制格式表示的IP地址输出。
输入格式：

输入在一行中给出32位二进制字符串。
输出格式：

在一行中输出十进制格式的IP地址，其由4个十进制数组成（分别对应4个8位的二进制数），中间用“.”分隔开。
输入样例：

11001100100101000001010101110010

输出样例：

204.148.21.114

#include 
#include 
int main()
{
	char a[33];
	int t=7;//当前处理的二进制位在8位中的位置
	int sum=0;//当前部分的十进制结果
	
	gets(a);
	for(int i=0;i<32;i++)
	{
		a[i]=a[i]-48;//将字符型的'0'~'1'转换成对应的整型数0~1
		sum+=a[i]*pow(2,t);
		
		if(t==0)//如果是8位中的最后一位
		{
		printf("%d",sum);
		t=7;
		sum=0;
		if(i!=31)
		printf(".");
		}
		else
		t--;
	}
}
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