2021-2022-2-第7次单元练习后记

2021-2022-2-第6次单元练习后记//Pintia

• 一个简单的说明
• • 7-1 苹果树 (10 分)
  • • 题面
    • • 输入格式:
      • 输出格式:
      • 输入样例:
      • 输出样例:
    • C++源码
    • • 一开始想当然把上上次的题目(一模一样)复制过来，才发现输入顺序是反的，上上次是在线做法，本题适合离线做法//当然你要事多我也不拦着
  • 7-2 计算书费 (10 分)
  • • 题面
    • • 输入格式:
      • 输出格式:
      • 输入样例:
      • 输出样例:
    • C++源码
  • 7-3 第几天 (10 分)
  • • 题面
    • • 输入格式:
      • 输出格式:
      • 输入样例:
      • 输出样例:
    • C++源码
  • 7-4 顺序查找 (10 分)
  • • 题面
    • • 输入格式:
      • 输出格式:
      • 输入样例:
      • 输出样例:
    • C++源码
    • • 老是忘记不合情况的语句判断输出，有点心急了
  • 7-5 交换最小值和最大值 (10 分)
  • • 题面
    • • 输入格式：
      • 输出格式：
      • 输入样例：
      • 输出样例：
    • C++源码
    • • 考虑的有点乱，好久才理清楚
  • 7-6 冒泡法排序 (10 分)
  • • 题面
    • • 输入格式：
      • 输出格式：
      • 输入样例：
      • 输出样例：
    • C++源码
    • • 说实话，如果不说本题，我都完全不记得冒泡这个粗俗的暴力排序(时间复杂度O(n^2^))，归并和快排还要堆，太香了！冒泡选择插空？什么玩意
  • 7-7 村长分奖金 (10 分)
  • • 题面
    • • 输入格式:
      • 输出格式:
      • 输入样例:
      • 输出样例:
    • C++源码
  • 7-8 又是摘苹果 (10 分)
  • • 题面
    • • 输入格式:
      • 输出格式:
      • 输入样例:
      • 输出样例:
    • C++源码
    • • 题目里终于出现贪心的思想了，我很欣慰，这是好的，然后借机复习了一下快速排序，好耶！
  • 7-9 合唱队 (10 分)
  • • 题面
    • • 输入格式:
      • 输出格式:
      • 输入样例:
      • 输出样例:
    • C++源码
    • • [NOIP2004 提高组] 合唱队形 原题数据加强版，预估达到了5k左右。
        

        btw，不给出数据范围是真的司马。
        

      • 剩下就只有感慨，没想到啊，时隔多年我这个机房摸鱼人，又摸到了提高组的水题。
        

        笑死，金典感叹青春了。
        

• 本次练习的反思
• 关于源码中read()函数的说明

一个简单的说明

主要以记录题目，分享源码为主
顺带记录做题心路历程
太久没有做题了，手生了，难免犯一些低级错误
最后，顺便对我的后续练习起到一个规划的作用

7-1 苹果树 (10 分) 题面

小鲁家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。

苹果成熟的时候，小鲁就会跑去摘苹果（不如我们去帮他吃掉）。

小鲁有个30厘米高的板凳，当他不能直接用手摘到苹果的时候，就会踩到板凳上再试试。

现在已知10个苹果到地面的高度，以及小鲁把手伸直的时候能够达到的最大高度，请帮小鲁算一下他能够摘到的苹果的数目。

假设他碰到苹果，苹果就会掉下来。

（苹果很配合哦）

输入格式:

输入包括两行数据。

第1行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。

第2行只包括一个100到120之间（包含100和120）的整数（单位：厘米），表示小鲁把手伸直的时候能够达到的最大高度。

输出格式:

输出包括一行，这一行只包含一个整数，表示小鲁能够摘到的苹果的数目。

输入样例:

100 200 150 140 129 134 167 198 200 111
110

输出样例:

5

C++源码

#include
#define MAXN 11 

inline int read(){
	int f=1,s=0;
	char k=getchar();
	while(k>'9'||k<'0'){if(k=='-')f=-1,k=getchar();}
	while(k>='0'&&k<='9'){s=(s<<3)+(s<<1)+k-'0';k=getchar();}
	return f*s;
}

int n,a,b,in[MAXN];

int main(){
	b=0;
	for(int i=1;i<=10;++i)in[i]=read();
	n=read();
	for(int i=1;i<=10;++i)
		if(in[i]<=n+30)b++;
	printf("%d",b);
	return 0;
}

一开始想当然把上上次的题目(一模一样)复制过来，才发现输入顺序是反的，上上次是在线做法，本题适合离线做法//当然你要事多我也不拦着 7-2 计算书费 (10 分) 题面

下面是一个图书的单价表： 计算概论 28.9 元/本 数据结构与算法 32.7 元/本 数字逻辑 45.6元/本 C++程序设计教程 78 元/本 人工智能 35 元/本 计算机体系结构 86.2 元/本 编译原理 27.8元/本 *** 作系统 43 元/本 计算机网络 56 元/本 JAVA程序设计 65 元/本 给定每种图书购买的数量，编程计算应付的总费用。

输入格式:

输入一行，包含10个整数(大于等于0，小于等于100)，分别表示购买的《计算概论》、《数据结构与算法》、《数字逻辑》、《C++程序设计教程》、《人工智能》、《计算机体系结构》、《编译原理》、《 *** 作系统》、《计算机网络》、《JAVA程序设计》的数量（以本为单位）。

每两个整数用一个空格分开。

输出格式:

输出一行，包含一个浮点数，表示应付的总费用。

精确到小数点后一位。

输入样例:

1 5 8 10 5 1 1 2 3 4

输出样例:

2140.2

C++源码

#include

double ans;
double in[]={0,28.9,32.7,45.6,78,35,86.2,27.8,43,56,65};//忘记了中括号，所以我是傻逼 
int a;

inline int read(){
	int f=1,s=0;
	char k=getchar();
	while(k>'9'||k<'0'){if(k=='-')f=-1,k=getchar();}
	while(k>='0'&&k<='9'){s=(s<<3)+(s<<1)+k-'0';k=getchar();}
	return f*s;
}

int main(){
	ans=0;
	for(int i=1;i<=10;++i){
		a=read();
		ans+=in[i]*a;
	}
	printf("%.1lf",ans);
	return 0;
}

7-3 第几天 (10 分) 题面

给定一个日期，输出这个日期是该年的第几天。

输入格式:

包含三个整数，表示年、月、日。

输出格式:

输出一行，表示该日期是当年的第几天。

输入样例:

2018 2 2

输出样例:

33

C++源码

#include

int n,m,d,ans;
int in[]={0,31,28,31,30,31,30,31,31,30,31,30,31};

inline int read(){
	int f=1,s=0;
	char k=getchar();
	while(k>'9'||k<'0'){if(k=='-')f=-1,k=getchar();}
	while(k>='0'&&k<='9'){s=(s<<3)+(s<<1)+k-'0';k=getchar();}
	return f*s;
}

int main(){
	ans=0;
	n=read(),m=read(),d=read();
	if(n%400==0||(n%4==0&&n%100!=0)){
		if(m>2)ans++;
	}
	for(int i=1;i<m;++i)ans+=in[i];
	ans+=d;
	printf("%d",ans);
	return 0;
} 

7-4 顺序查找 (10 分) 题面

在一个序列（下标从1开始）中查找一个给定的值，输出第一次出现的位置。

输入格式:

第一行包含一个正整数n，表示序列中元素个数。

1 <= n <= 10000。

第二行包含n个整数，依次给出序列的每个元素，相邻两个整数之间用单个空格隔开。

第三行包含一个整数x，为需要查找的特定值。

输出格式:

若序列中存在x，输出x第一次出现的下标；否则输出"not found"。

输入样例:

5
2 3 6 7 3
3

输出样例:

2

C++源码

#include
#define MAXN 1001

inline int read(){
	int f=1,s=0;
	char k=getchar();
	while(k>'9'||k<'0'){if(k=='-')f=-1,k=getchar();}
	while(k>='0'&&k<='9'){s=(s<<3)+(s<<1)+k-'0';k=getchar();}
	return f*s;
}

int n,in[MAXN],ans,want;

int main(){
	ans=0;
	n=read();
	for(int i=1;i<=n;++i)in[i]=read();
	want=read();
	for(int i=1;i<=n;++i)if(in[i]==want){
		ans=i;
		break;
	}
	if(!ans)printf("not found");//老是忘记这个判断 
	else printf("%d",ans);
	return 0;
}

老是忘记不合情况的语句判断输出，有点心急了 7-5 交换最小值和最大值 (10 分) 题面

本题要求编写程序，先将输入的一系列整数中的最小值与第一个数交换，然后将最大值与最后一个数交换，最后输出交换后的序列。

注意：题目保证最大和最小值都是唯一的。

输入格式：

输入在第一行中给出一个正整数N（≤10），第二行给出N个整数，数字间以空格分隔。

输出格式：

在一行中顺序输出交换后的序列，每个整数后跟一个空格。

输入样例：

5
8 2 5 1 4

输出样例：

1 2 5 4 8

C++源码

#include
#define MAXN 11

inline int read(){
	int f=1,s=0;
	char k=getchar();
	while(k>'9'||k<'0'){if(k=='-')f=-1,k=getchar();}
	while(k>='0'&&k<='9'){s=(s<<3)+(s<<1)+k-'0';k=getchar();}
	return f*s;
}

int n,in[MAXN],maxx,maxn,minx,minn,firsts,lasts;

int main(){
	maxx=maxn=minn=0;
	minx=19260817;
	n=read();
	for(int i=1;i<=n;++i){
		in[i]=read();
		if(in[i]<minx){
			minx=in[i];
			minn=i;
		}
	}
	in[1]^=in[minn];
	in[minn]^=in[1];
	in[1]^=in[minn];
	for(int i=1;i<=n;++i){
		if(in[i]>maxx){
			maxx=in[i];
			maxn=i;
		}
	}
	in[n]^=in[maxn];
	in[maxn]^=in[n];
	in[n]^=in[maxn];
	for(int i=1;i<=n;++i)printf("%d ",in[i]);
	return 0;
}

考虑的有点乱，好久才理清楚 7-6 冒泡法排序 (10 分) 题面

将N个整数按从小到大排序的冒泡排序法是这样工作的：从头到尾比较相邻两个元素，如果前面的元素大于其紧随的后面元素，则交换它们。

通过一遍扫描，则最后一个元素必定是最大的元素。

然后用同样的方法对前N−1个元素进行第二遍扫描。

依此类推，最后只需处理两个元素，就完成了对N个数的排序。

本题要求对任意给定的K（

输入格式：

输入在第1行中给出N和K（1≤K

输出格式：

在一行中输出冒泡排序法扫描完第K遍后的中间结果数列，数字间以空格分隔，但末尾不得有多余空格。

输入样例：

6 2
2 3 5 1 6 4

输出样例：

2 1 3 4 5 6

C++源码

#include
#define MAXN 101

inline int read(){
	int f=1,s=0;
	char k=getchar();
	while(k>'9'||k<'0'){if(k=='-')f=-1,k=getchar();}
	while(k>='0'&&k<='9'){s=(s<<3)+(s<<1)+k-'0';k=getchar();}
	return f*s;
}

int n,k,in[MAXN];

int main(){
	n=read(),k=read();
	for(int i=1;i<=n;++i)in[i]=read();
		for(int j=0;j<n;++j){
			for(int w=2;w<=n-j;++w){			
				if(in[w-1]>in[w]){
					in[w]^=in[w-1];
					in[w-1]^=in[w];
					in[w]^=in[w-1];
				}
			}
			if(j==k-1)break;
		}
	for(int i=1;i<n;++i)printf("%d ",in[i]);
	printf("%d",in[n]);//末尾不得有多余空格,nmsl 
	return 0;
}

说实话，如果不说本题，我都完全不记得冒泡这个粗俗的暴力排序(时间复杂度O(n²))，归并和快排还要堆，太香了！冒泡选择插空？什么玩意 7-7 村长分奖金 (10 分) 题面

过年了，村里要庆祝一下。

村长对村民说：村里有一笔钱作为奖金。

让每个人写一个纸条上来，谁写的数与奖金最接近，就算猜中，这笔奖金就归谁，如果有多个人猜中，则平分这笔钱。

现在让我们来写一段程序算算都有哪些人得到了奖金？得到多少？

输入格式:

第一行包含2个整数 n,m，分别表示村民人数和村里的奖金总数。

第二行包含n个整数，整数之间以一个空格分开。

表示1号,2号，。

。

。

，n号村民猜测的奖金数。

（1<=n<=5000）

输出格式:

输出分两行。

第一行包含若干整数，表示得到奖金的村民编号(数据之间有一个空格，最后一个数后面无空格！！！)， 第二行包含一个实数（保留1位小数），表示人均奖金金额。

输入样例:

10 100
50 60 70 80 90 90 110 120 130 140

输出样例:

在这里给出相应的输出。

例如：

5 6 7
33.3

C++源码

#include
#include
#define MAXN 5001

inline int read(){
	int f=1,s=0;
	char k=getchar();
	while(k>'9'||k<'0'){if(k=='-')f=-1,k=getchar();}
	while(k>='0'&&k<='9'){s=(s<<3)+(s<<1)+k-'0';k=getchar();}
	return f*s;
}

int n,m,in[MAXN],maxx,maxn,minx,minn,need,couts,an[MAXN],cnt;
double ans=0;

int main(){
	maxx=minx=need=couts=cnt=0;
	maxn=minn=19260817;
	n=read(),m=read();
	for(int i=1;i<=n;++i){
		in[i]=read();
		if(in[i]<=m&&m-in[i]<minn){
			minn=m-in[i];
			minx=in[i];
		}
		if(in[i]>=m&&in[i]-m<maxn){
			maxn=in[i]-m;
			maxx=in[i];
		}
	}
	if(maxn>minn){
	need=minx;
	for(int i=1;i<=n;++i)
		if(in[i]==need){
			couts++;
			an[++cnt]=i;
		}
	}
	else if(minn>maxn){
		need=maxx;
		for(int i=1;i<=n;++i)
		if(in[i]==need){
			couts++;
			an[++cnt]=i;
		}
	}
	else {
		for(int i=1;i<=n;++i)
		if(in[i]==maxx||in[i]==minx){
			couts++;
			an[++cnt]=i;
		}
	}
	for(int i=1;i<cnt;++i)printf("%d ",an[i]);
	printf("%d",an[cnt]);//傻逼般的最后一个无空格 
	putchar('\n');
	m*=10;
	ans=m/couts*1.0;
	ans/=10;
	printf("%.1lf",ans);
	return 0;
}

7-8 又是摘苹果 (10 分) 题面

又是一年秋季时，陶陶家的苹果树结了n个果子。

陶陶又跑去摘苹果，这次她有一个a公分的椅子。

当他手够不着时，他会站到椅子上再试试。

陶陶之前搬凳子，力气只剩下s了。

当然，每次摘苹果时都要用一定的力气。

陶陶想知道在s<0之前最多能摘到多少个苹果。

现在已知n个苹果到达地上的高度xi，椅子的高度a，陶陶手伸直的最大长度b，陶陶所剩的力气s，陶陶摘一个苹果需要的力气yi，求陶陶最多能摘到多少个苹果。

。

输入格式:

第1行：两个数 苹果数n，力气s。

第2行：两个数 椅子的高度a，陶陶手伸直的最大长度b。

第3行~第3+n-1行：每行两个数 苹果高度xi，摘这个苹果需要的力气yi。

输出格式:

只有一个整数，表示陶陶最多能摘到的苹果数。

输入样例:

8 15
20 130
120 3
150 2
110 7
180 1
50 8
200 0
140 3
120 2

输出样例:

4

C++源码

//贪心！终于有点意思了，笑死
//需要复习快排，考完试再写 
#include
#define MAXN 5001//增大到5k才过，不然都说段错误，神经病啊，没给数据范围 

int ap[MAXN][2];
int n,s,a,b,couts;

inline int read(){
	int f=1,s=0;
	char k=getchar();
	while(k>'9'||k<'0'){if(k=='-')f=-1,k=getchar();}
	while(k>='0'&&k<='9'){s=(s<<3)+(s<<1)+k-'0';k=getchar();}
	return f*s;
}

void qsort(int left,int right){ 
	if(left>right)return;
	int temp1=ap[left][0],temp2=ap[left][1];
	int i=left;
	int j=right;
	while(i!=j){
		while(i<j&&ap[j][1]>=temp2)j--;
		while(i<j&&ap[i][1]<=temp2)i++;
		if(i<j){
			ap[i][0]^=ap[j][0];
			ap[j][0]^=ap[i][0];
			ap[i][0]^=ap[j][0];
			ap[i][1]^=ap[j][1];
			ap[j][1]^=ap[i][1];
			ap[i][1]^=ap[j][1];
		}
	}
	ap[left][0]=ap[i][0];
	ap[i][0]=temp1;
	ap[left][1]=ap[i][1];
	ap[i][1]=temp2;
	qsort(left,i-1);
	qsort(i+1,right);
}

int main(){
	couts=0;
	n=read(),s=read();
	a=read(),b=read();
	for(int i=1;i<=n;++i){
		ap[i][0]=read();
		ap[i][1]=read();
	}
	qsort(1,n);
	for(int i=1;i<=n;++i){
		if(ap[i][0]<=a+b&&s>=ap[i][1]){
			couts++;
			s-=ap[i][1];
		}
	}
	printf("%d",couts);
	return 0;
} 

题目里终于出现贪心的思想了，我很欣慰，这是好的，然后借机复习了一下快速排序，好耶！ 7-9 合唱队 (10 分) 题面

合唱队共有N个人（N 为奇数）。

为了准备一次演出，老师开始为她们安排合唱队形了。

大家都知道，合唱队形通常是中间高两端低的。

老师是这样安排他们的队形的：先让所有的同学按高个儿在前的顺序排成一队。

然后，最高的那位同学单独站出来，这是合唱队形的中心，再让第二位同学站在他的左手边，让第三位同学站在他的右手边，再依次向两端安排其他人…… 事先给定所有人的身高，请输出他们站成合唱队形之后的身高顺序。

输入格式:

第一行是一个整数 ，表示合唱队的总人数，已知 N 为奇数，且 1 ≤ N ≤ 51 。

第二行是 N 个整数，表示以厘米为单位的所有人的身高。

输出格式:

只有 N 个整数，表示她们按老师的要求站成合唱队形之后的身高顺序。

最后一个数据后面无空格

输入样例:

7
154 160 157 162 159 152 163

输出样例:

152 157 160 163 162 159 154

C++源码

#include
#define MAXN 101

int n,ap[MAXN],ans[MAXN],mid,couts;

inline int read(){
	int f=1,s=0;
	char k=getchar();
	while(k>'9'||k<'0'){if(k=='-')f=-1,k=getchar();}
	while(k>='0'&&k<='9'){s=(s<<3)+(s<<1)+k-'0';k=getchar();}
	return f*s;
}

void qsort(int left,int right){ 
	if(left>right)return;
	int temp=ap[left];
	int i=left;
	int j=right;
	while(i!=j){
		while(i<j&&ap[j]<=temp)j--;
		while(i<j&&ap[i]>=temp)i++;
		if(i<j){
			ap[i]^=ap[j];
			ap[j]^=ap[i];
			ap[i]^=ap[j];
		}
	}
	ap[left]=ap[i];
	ap[i]=temp;
	qsort(left,i-1);
	qsort(i+1,right);
}

int main(){
	n=read();
	mid=n/2+1;
	for(int i=1;i<=n;++i)ap[i]=read();;
	qsort(1,n);
	ans[mid]=ap[1];
	for(int i=2;i<=n;++i){
		couts=i/2;
		if(i&1)ans[mid-couts]=ap[i];
		else ans[mid+couts]=ap[i];
	}
	for(int i=1;i<n;++i)printf("%d ",ans[i]);
	printf("%d",ans[n]);
	return 0;
} 

[NOIP2004 提高组] 合唱队形 原题数据加强版，预估达到了5k左右。

btw，不给出数据范围是真的司马。

剩下就只有感慨，没想到啊，时隔多年我这个机房摸鱼人，又摸到了提高组的水题。

笑死，金典感叹青春了。

本次练习的反思

周末期中考试，所以做到最后俩题，因为排序忘得差不多了，所以摸了
其实在想，c语言的练习，我拿c++的stl的sort去写，是不是有一点ntr
最后高数考试果然寄了，这个练习的速通也寄了。

寄寄寄！

关于源码中read()函数的说明

read()函数为自行定义的一个快速读入整数的函数，不熟悉快读的朋友可以自行改为scanf()语句。