A: 递归求解

题目描述

请使用递归编写一个程序求如下表达式的计算结果： 

S(1) = 1/2

S(2) = 1/2 + 1/6

S(3) = 1/2 + 1/6 + 1/12

S(4) = 1/2 + 1/6 + 1/12 + 1/20

......

S(n) = 1/2 + 1/6 + 1/12 + 1/20 + 1/30 + ......

输入n (1<n<=1000)，输出表达式S(n)的值（精确到小数点后六位）。

请编写一个递归程序实现该功能。

输入

单组输入，输入一个正整数n，1<n<=1000。

输出

输出表达式S(n)的计算结果（精确到小数点后六位）。

样例输入 Copy

2

样例输出 Copy

0.666667 

 思路：观察一下得知分母是项数*(项数+1)得来的

<code>#include<stdio.h>

#define long long ll;

double fun(int n,int m,double s){

if(m>n){

return s;

}

else{

fun(n,m+1,s+1.0/(m*(m+1)));

}

}

int main(){

int n;

scanf("%d",&n);

printf("%lf\n",fun(n,2,0.5));

return 0;

}

 B: 挑选奖品

题目描述

X星人参加了一档幸运大抽奖节目，凭借无敌好运气中了一等奖。节目组给他准备了一个奖品箱，这个箱子中一共有M个格子，每个格子中只能放一个奖品。

现在一共有N个不同的奖品供X星人挑选，不同的奖品其价值不一定相等。

“贪心的”X星人希望所挑选的奖品的价值和最大，需要你编写一个程序帮他计算出所能得到的最大价值和。

输入

单组输入。

第1行包含两个正整数M和N，分别表示奖品箱中格子的数量和奖品的总数。（1< M<=10^5且1<N<=10^5）

第2行包含N个正整数，分别表示N个奖品的价值，两两之间用空格隔开。

输出

奖品箱中所有奖品的最大价值和。

样例输入 Copy

3 5

1 3 2 6 5

样例输出 Copy

14

思路：因为挑选价值最大，所以我们从价值最大的开始选，总共选m个。因为数据范围是1e5，所以冒泡排序On2的做法会超时，我们采用快速排序，如果用c++的直接sort函数就行了，并且极限数据会爆int的数据范围，所以采用long long。 

#include<stdio.h>

#define ll long long

int a[100005];

void quickSort(int l,int r){//是从大到小的快速排序

if(l>r){

return;

}

int tt=a[l];

int i=l;

int j=r;

int t;

while(i!=j){

while(i<j&&a[j]<=tt){

j--;

}

while(i<j&&a[i]>=tt){

i++;

}

if(i<j){

t=a[i];

a[i]=a[j];

a[j]=t;

}

}

a[l]=a[i];

a[i]=tt;

quickSort(l,i-1);

quickSort(i+1,r);

}

int main(){

int m,n;

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

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

scanf("%d",&a[i]);

}

quickSort(1,n);

ll s=0;

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

s+=a[i];

}

printf("%lld\n",s);

return 0;

}

 C: 排列蛋卷

题目描述

刚考完研的TC同学这段时间在家闲得慌，因此他决定学点新手艺。今天他学习的内容是：做蛋卷。

由于是第一次做蛋卷，TC同学做出来蛋卷长短不一。看着这些长度都不一样的蛋卷，TC同学的强迫症又犯了。他希望能够拿出其中部分蛋卷，使得留下来的蛋卷能够按照长度从大到小的次序排列。

请问他最少需要拿出多少根蛋卷？

输入

单组输入，对于每一组测试数据，第1行N表示蛋卷的总数量（n<=1000)。 

第2行包含N个正整数，分别表示每一根蛋卷的长度。（单位：厘米） 

保证在同一组输入数据中每一根蛋卷的长度均不一样。

输出

输出最少需要拿出的蛋卷数量。

样例输入 Copy

5

15 18 17 11 12

样例输出 Copy

2

思路：看完题发现就是最长上升子序列改成了最长下降子序列，然后用n减去长度就行了，其实是一样的，数据范围也不大可以采用On2的做法

#include<stdio.h>

#define ll long long

int a[1005],dp[1005];

int max(int a,int b){

return a>b?a:b;

}

int main(){

int n;

scanf("%d",&n);

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

scanf("%d",&a[i]);

}

int s=0;

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

dp[i]=1;

for(int j=0;j<i;j++){

if(a[i]<a[j]){

dp[i]=max(dp[i],dp[j]+1);

}

}

s=max(s,dp[i]);

}

printf("%d\n",n-s);

return 0;

}

D: 最大收益

题目描述

小X是一位精明的投资人，他每次都能够做出正确的投资判断。

现在有N个项目，每个项目的总投资额和总收益已知，并且每一个项目都允许小X只投资一部分，当然也就只能拿到一部分收益。 

现在小X决定拿出M万元钱来进行投资，请你帮他设计一个算法来计算最大收益和。

输入

单组输入，对于每一组数据，第1行包含两个正整数，分别是M和N，其中M<=10^6，N<=100。

接下来N行每行均包含两个正数（不一定是正整数），第1数字表示第N个项目的总投资额（万元），第2个数字表示第N个项目的总收益（万元），两个数字之间用空格隔开。 

输出

小X可以获得的最大收益和（万元，结果四舍五入保留两位小数）。

样例输入 Copy

100 4

50 10

20 10

40 10

50 20

样例输出 Copy

37.50

思路：首先计算每个项目单位投资的收益，然后按照单位收益从高到低排序，优先投资单位收益高的项目(使用结构体排序)，这样可以就最大化我们的总收益。 

#include<stdio.h>

#define ll long long

typedef struct S{

double u,v,s;

}ss;

int main(){

int m,n;

ss a[1005],t;

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

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

scanf("%lf%lf",&a[i].u,&a[i].v);

a[i].s=a[i].v/a[i].u;

}

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

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

if(a[j].s<a[j+1].s){

t=a[j];

a[j]=a[j+1];

a[j+1]=t;

}

}

}

double mm=0;

double sum=m;

for(int i=0;i<n&&sum>0;i++){

if(sum>=a[i].u){

mm+=a[i].v;

sum-=a[i].u;

}

else{

mm+=a[i].s*sum;

sum=0;

}

}

printf("%.2lf\n",mm);

return 0;

}

 E: 最小积分

题目描述

Kimi和Sunny决定在线组队玩一个数字游戏，该游戏的规则如下：

(1) 游戏系统随机生成两组正整数，每组N个数字，两组正整数可能不一样；

(2) 每个游戏团队两个人，每个人拿其中一组数字；

(3) 每一轮两个人从自己的那组数字中各取出一个数字，将两个数字相乘作为这一轮的积分，取出的数字不能再重复使用；

(4) 一共玩N轮，将每轮的积分求和，得到一个总积分；

(5) 总积分最小的队伍获胜。

现在需要你编写一个程序帮Kimi和Sunny计算出最小积分和。

输入

单组输入。

第1行输入一个正整数N，N不超过100。

第2行输入N个不超过1000的正整数，表示Kimi拿到的数字，两两之间用空格隔开。

第3行输入N个不超过1000的正整数，表示Sunny拿到的数字，两两之间用空格隔开。

输出

输出最小积分和。

样例输入 Copy

3

3 1 2

4 3 5

样例输出 Copy

22

思路：这题就是一个贪心，我们使得最小积分和最小，那就让最大的去跟最小的乘以此类推。两个排序 一个从大到小 一个从小到大就解决了

数据范围不大，均可以采用冒泡排序

#include<stdio.h>

#define ll long long

int a[105],b[105];

int main(){

int n;

scanf("%d",&n);

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

scanf("%d",&a[i]);

}

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

scanf("%d",&b[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=0;i<n-1;i++){

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

if(b[j]<b[j+1]){

int t=b[j];

b[j]=b[j+1];

b[j+1]=t;

}

}

}

int s=0;

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

s+=a[i]*b[i];

}

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

return 0;

}

 F: 数字迷宫

题目描述

X星有一个很神秘的数字迷宫。这个迷宫是一个由若干小方格区域组成的矩阵，一共包含M行和N列。每一个小方格中都有一个正整数，表示经过这个方格区域所需要的能量值。

现在小Z从最左边的列任选一个方格作为出发点，每一次只能向右边、右上或右下方向走一格，但不能走出数字迷宫，最终要到达最右边的列。

请你编写一个程序，输出消耗的总能量最少的那条路线所对应的总能量值（总能量值包含起点方格和终点方格所需能量值）。

输入

单组输入。

第1行输入两个正整数M和N，分别表示数字迷宫的行和列，M和N均不超过1000，两者之间用一个英文空格隔开。

接下来M行，每行包含N个正整数，每个正整数对应经过一个小方格区域所需的能量值，每个能量值均不超过100。同一行的两个正整数之间用一个英文空格隔开。

输出

输出一个正整数，表示总能量最少的那条路线所对应的总能量值。

样例输入 Copy

3 3

3 4 1

6 1 8

3 7 2

样例输出 Copy

5

 思路：这题是动态规划，用dp[i][j]表示到达当前位置前的最小能量，则得到dp[i][j]=a[i][j]+min(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1])，这个值的贡献就是a[i][j]+从三个方向来的最小值，特判一下第一列和最后一列只有两个方向来的。

#include<stdio.h>

#define ll long long

int a[1005][1005];

int dp[1005][1005];

int min(int a,int b,int c){

int t=a<b?a:b;

return t<c?t:c;

}

int mmin(int a,int b){

return a<b?a:b;

}

int main(){

int m,n;

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

for(int i=0;i<m;i++){

for(int j=0;j<n;j++){

scanf("%d",&a[i][j]);

}

}

for(int i=0;i<m;i++){

dp[i][0]=a[i][0];

}

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

for(int i=0;i<m;i++){

if(i==0){

dp[i][j]=a[i][j]+mmin(dp[i][j-1],dp[i+1][j-1]);

}

else if(i==m-1){

dp[i][j]=a[i][j]+mmin(dp[i][j-1],dp[i-1][j-1]);

}

else{

dp[i][j]=a[i][j]+min(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1]);

}

}

}

int mm=dp[0][n-1];

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

if(dp[i][n-1]<mm){

mm=dp[i][n-1];

}

}

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

return 0;

}

G:又见小青蛙跳台阶(两种做法)

不管是什么做法都算是斐波那契递推式

题目描述

一个有N级台阶的楼梯，一只小青蛙的初始位置是第0级台阶，它一次可以跳1级台阶，也可以一次跳2级台阶。

现在已知这个楼梯中有两级是坏的，分别是第X级和第Y级，且1<X<Y<N。

请问小青蛙跳到第N级台阶一共有多少种跳法？

输入

单组输入。

输入一行包含三个正整数X，Y和N，N<=20，1<X<Y<N，两两之间用英文空格隔开。

输出

输出小青蛙跳到第N级台阶的跳法数。

样例输入 Copy

2 4 7

样例输出 Copy

2

思路1： 这个递推遇到坏的就是0，直接continue就行了，因为全局数组默认初始值为0

#include<stdio.h>

#define ll long long

int a[30];

int main(){

int x,y,n;

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

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

if(i==x||i==y){

continue;

}

else{

if(i==1){

a[1]=1;

continue;

}

if(i==2){

a[2]=2;

continue;

}

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

}

}

printf("%d\n",a[n]);

return 0;

}

思路2：利用组合数的知识，第一个坏台阶之前的跳法*中间台阶的跳法*第二个坏台阶之后的跳法

#include<stdio.h>

#define ll long long

int a[30];

int main(){

int x,y,n;

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

if(x+1==y){

printf("0\n");

return 0;

}

a[1]=1,a[2]=1;

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

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

}

printf("%d\n",a[x]*a[y-x-1]*a[n-y]);

return 0;

}

H: X星礼物问题

题目描述

新的一年又到了，X星最大的企业XYZ公司决定给X星第一小学的小朋友们送一批礼物。

每个小朋友最多只能得到一件礼物（也有可能得不到）。每一件礼物都有一个“喜爱度”，“喜爱度”是一个1-100之间（包含1和100）的数字。

每位小朋友对于礼物的“喜爱度”都有一个预期值，当然有的小朋友预期值高，也有的小朋友预期值低。

XYZ公司希望能够尽量满足每个小朋友的“喜爱度”预期值，送给某位小朋友的礼物的“喜爱度”不能低于这位小朋友的“喜爱度”预期值。

现在一共有M件礼物要发给N个小朋友（N和M均不超过1000），告诉你这M件礼物的“喜爱度”以及N个小朋友的“喜爱度”预期值，请你编写一个程序，统计这M件礼物最多可以满足多少个小朋友的预期值，请输出最多可以满足的人数。

输入

单组输入。

第1行输入两个正整数M和N，分别表示礼物的数量和小朋友的个数，N和M均不超过1000，二者用英文空格隔开。

第2行输入M个正整数，表示M件礼物的“喜爱度”值，每个正整数均不超过100，两两之间用英文空格隔开。

第3行输入N个正整数，表示N个小朋友的“喜爱度”预期值，每个正整数均不超过100，两两之间用英文空格隔开。

输出

输出最多可以满足的小朋友的人数。

样例输入 Copy

3 3

4 1 8

5 2 6

样例输出 Copy

2

 思路：均先从小到大排序，数据不大，可以使用冒泡排序，然后对礼物的预期值与实际值进行匹配，不满足则预期值增大，直到最后一个礼物。

#include<stdio.h>

#define ll long long

int a[1005],b[1005];

int main(){

int m,n;

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

for(int i=0;i<m;i++){

scanf("%d",&a[i]);

}

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

scanf("%d",&b[i]);

}

for(int i=0;i<m-1;i++){

for(int j=0;j<m-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<n-1;i++){

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

if(b[j]>b[j+1]){

int t=b[j];

b[j]=b[j+1];

b[j+1]=t;

}

}

}

int s=0;

int j=0;

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

while(j<m&&a[j]<b[i]){

j++;

}

if(j==m){

break;

}

s++;

j++;

}

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

return 0;

}

I:HNUCM的漂亮石头

题目描述

Kimi在HNUCM的美丽校园中散步，他发现在HNUCM的新月湖旁边有很多漂亮的小石头，他想捡一些小石头回去放到新买的花盆中。

他今天带了一个小塑料袋来装石头，但是该塑料袋能够装的石头的总重量不能超过某一个阈值，要不塑料袋肯定会坏掉，因此Kimi想选一些“高质量”的石头。

已知每一块小石头都有一个重量，Kimi还根据小石头的漂亮程度给每一块小石头打了一个分，我们就把这个打分叫做“漂亮度”吧。

Kimi希望塑料袋中的小石头的“漂亮度”之和达到最大值，现在需要请你编写一个程序帮Kimi计算出可以得到的“漂亮度”之和的最大值。

输入

单组输入。

第1行输入一个正整数n，表示可供选择的小石头总数量。(1<=n<=1000)

第2行输入一个正整数m，表示小塑料袋可以承受的最大重量。(1<=m<=100)

接下来n行，每行输入两个正整数表示某一块小石头的重量和漂亮度，第1个正整数表示重量，第2个正整数表示漂亮度，两者之间用英文空格隔开。

输出

输出小塑料袋中装入的石头的“漂亮度”之和的最大值。

样例输入 Copy

5

10

3 8

2 10

5 13

4 30

3 6

样例输出 Copy

48

思路：01背包问题  emm就这样 

#include<stdio.h>

#define ll long long

int a[1005][2];

int dp[105];

int max(int a,int b){

return a>b?a:b;

}

int main(){

int n,m;

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

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

scanf("%d%d",&a[i][0],&a[i][1]);

}

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

for(int j=m;j>=a[i][0];j--){

dp[j]=max(dp[j],dp[j-a[i][0]]+a[i][1]);

}

}

printf("%d\n",dp[m]);

return 0;

}

J:HNUCM的批改作文(已修正)

题目描述

HNUCM的小王老师给同学们布置了一道小作文题，要求所有同学同时提交并现场批改。

批改完的同学即可以下课，否则就需要等待老师把自己的作文批改完才能够下课。

交小作文的时间到了，N个同学同时把作文提交给了小王老师，小王老师根据大家写的字数估算了一下批改时间（单位：分钟），现在请你编写一个程序帮助小王老师做一个决策，使得所有同学等待作文批改的平均时间最少，请输出最少平均等待时间（单位：分钟）。

输入

单组输入。

第1行输入一个不超过100的正整数N。

第2行输入N个不超过20的正整数，每一个正整数对应一个同学的作文批改时间（单位：分钟），两个正整数之间用英文空格分隔。

输出

输出所有同学的作文都批改完时的最少平均等待时间（单位：分钟），结果四舍五入保留两位小数。

样例输入 Copy

3

10 5 20

样例输出 Copy

18.33 

思路：理解一下题目的意思，就是你前面一个人在等的时候，其实我们后面的人都在等，这个时间都是要算上的。数据不大冒泡排序

#include<stdio.h>

#define ll long long

int a[105];

int main(){

int n;

scanf("%d",&n);

double f=0,s=0;

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=0;i<n;i++){

s+=a[i];

f+=s;

}

printf("%.2lf",f/n);

return 0;

}

 考试顺利！