SDUTOJ 《程序设计基础(B)Ⅱ》 实验 5 6 难度较大题目记录

面对机测,还是真香了QAQ

0.gif

删数问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

键盘输入一个高精度的正整数n(≤100位),去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的n与s,寻找一种方案,使得剩下的数字组成的新数最小。

Input

输入有多组 每组包括原始数n,要去掉的数字数s;

Output

输出去掉s个数后最小的数

Sample Input

178543  4

Sample Output

13

Reference Code

#include<stdio.h>
#include<string.h>
int main()
{
    int i,s,len,j;
    char a[102];
    while (~scanf("%s %d",a,&s))
    {
        while (s--)
        {
            i=0;
            len=strlen(a);
            while (i<len&&a[i]<=a[i+1]) i++;
            while (i<len)
            {
                a[i]=a[i+1];
                i++;
            }
        }
        while(a[0]!='\0')//格式化输出结果,把输出结果前的0去掉,如0058->58
        {
            i=0;
            if (a[i]=='0'&&a[i+1]!='\0')
            {
                while (a[i]!='\0')
                {
                    a[i]=a[i+1];
                    i++;
                }
            }
            else break;
        }
        printf("%s\n",a);
    }
    return 0;
}

活动选择

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

​ 学校的大学生艺术中心周日将面向全校各个学院的学生社团开放,但活动中心同时只能供一个社团活动使用,并且每一个社团活动开始后都不能中断。现在各个社团都提交了他们使用该中心的活动计划(即活动的开始时刻和截止时刻)。请设计一个算法来找到一个最佳的分配序列,以能够在大学生艺术中心安排不冲突的尽可能多的社团活动。
比如有5个活动,开始与截止时刻分别为:

img

最佳安排序列为:1,4,5。

Input

第一行输入活动数目n(0<n<100);
以后输入n行,分别输入序号为1到n的活动使用中心的开始时刻a与截止时刻b(a,b为整数且0<=a,b<24,a,b输入以空格分隔)。

Output

输出最佳安排序列所包含的各个活动(按照活动被安排的次序,两个活动之间用逗号分隔)。

Sample Input

6
8 10
9 16
11 16
14 15
10 14
7 11

Sample Output

1,5,4

Reference Code

#include<stdio.h>
struct
{
    int start;
    int end;
    int no;
    int select;
}ying[101],t;

int main()
{
    int n,i,j,last;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d %d",&ying[i].start,&ying[i].end);
        ying[i].no=i+1;
        ying[i].select=0;
    }
    for (i=0;i<n-1;i++)
    {
        for (j=0;j<n-i-1;j++)
        {
            if (ying[j].end>ying[j+1].end)
            {
                t=ying[j];
                ying[j]=ying[j+1];
                ying[j+1]=t;
            }
        }
    }
    last=0;
    for (i=0;i<n;i++)
    {
        if (ying[i].start>=last)
        {
            ying[i].select=1;
            last=ying[i].end;
        }
    }
    printf("%d",ying[0].no);//第一个一定选中,所以直接输出
    for (i=1;i<n;i++)
    {
        if (ying[i].select==1)
        {
            printf(",%d",ying[i].no);
        }
    }
    printf("\n");
    return 0;
}

区间覆盖问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

用i来表示x坐标轴上坐标为[i-1,i]的长度为1的区间,并给出n(1≤n≤200)个不同的整数,表示n个这样的区间。

现在要求画m条线段覆盖住所有的区间,

条件是:每条线段可以任意长,但是要求所画线段的长度之和最小,

并且线段的数目不超过m(1≤m≤50)。

Input

输入包括多组数据,每组数据的第一行表示区间个数n和所需线段数m,第二行表示n个点的坐标。

Output

每组输出占一行,输出m条线段的最小长度和。

Sample Input

5 3
1 3 8 5 11

Sample Output

7

Reference Code

#include<stdio.h>
void sort(int a[],int n)
{
    int i,j,t;
    for (i=0;i<n-1;i++)
    {
        for (j=0;j<n-i-1;j++)
        {
            if (a[j]<a[j+1])
            {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }
}

int main()
{
    int n,m,i,j,t,num,len;
    while(~scanf("%d %d",&n,&m))
    {
        int pos[201];
        int dis[201];
        for (i=0;i<n;i++)
        {
            scanf("%d",&pos[i]);
        }
        sort(pos,n);//给的数据顺序可能是乱的,因此进行排序
        for (i=0;i<n-1;i++)
        {
            dis[i]=pos[i]-pos[i+1]-1;//1-2和2-3区间的距离是0,要减去1
        }
        sort(dis,n-1);
        len=pos[0]-pos[n-1]+1;//测算整个线段的长度,两端的也要加上
        num=1;
        i=0;
        while (num<m&&dis[i]>0)
        {
            num++;
            len-=dis[i];
            i++;
        }
        printf("%d\n",len);
    }
    return 0;
}

最少拦截系统

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.

怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

Input

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

Output

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Sample Input

8 389 207 155 300 299 170 158 65

Sample Output

2

Reference Code

#include<stdio.h>
int main()
{
    int n,h[10000],i,t,x,flag,min;
    while (~scanf("%d",&n))
    {
        t=0;
        while (n--)
        {
            scanf("%d",&x);
            flag=0;
            min=30000;
            for (i=0;i<t;i++)
            {
                if (x<=h[i]&&min>h[i]-x)//如果可以拦截,要选择一个和当前高度个目标导弹高度差最小的
                {
                    min=h[i]-x;//如果可以拦截,要选择一个和当前高度个目标导弹高度差最小的
                    h[i]=x;
                    flag=1;
                }
            }
            if (flag==0)
            {
                h[t]=x;
                t++;
            }
        }
        printf("%d\n",t);
    }
    return 0;
}

悼念512汶川大地震遇难同胞

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

时间:2008年5月16日(震后第4天)

地点:汶川县牛脑寨

人物:羌族老奶奶

【转载整理】牛脑寨是一个全村600多人的羌族寨子,震后几天,这里依然能常常听到隆隆的声音,那是对面山上石头不断滑落的声音。在完成整个突击队的抢修移动基站的任务后,我提着相机开始记录这里的受创情况。

突然,我的视线里出现一个羌族老人,这让我无比的震惊,要知道,那是一个极陡的坡,这个佝偻着腰的老人是怎么艰难地爬上来的?她上来做什么?

老人背后是极陡的坡,她只有一只眼睛有依稀的视力,望着满地废墟,她徘徊了很久。家在哪里,她极力地用很低的视力找寻着。她曾经的家就在旁边,但是满目废墟已经让老人看不出来。她举目远眺,期望那里能看到家的一点点痕迹。原来家就在旁边,左手抓住一个房橼,努力让自己站住,地震过去三天了,她第一次回到曾经的家。

一个倒塌的柜子,里面装着一丝希望,老人很吃力地搬动掩盖在柜子上的薪柴。老人找到一把木匠用的刨子,老泪纵横,或许有哪个逝去的亲人是木匠。睹物思人,逝者已矣。

继续找,一把散碎的挂面出现在我的眼前。她颤颤巍巍地捞起铺满灰尘的挂面,再次流出了眼泪......

看着她仔细地把挂面放进胸前的围腰里,我顿然感觉到,这是老人在得到外援之前赖以生存的口粮了,如果不是交通中断,外部救援进不来,老人家又何必拖着80多岁的躯体,强忍失去亲人的痛苦,重新回到这夺取她亲人生命的废墟,寻找这点点挂面?老人是真饿了......

老人佝偻着腰,低声喃喃地念着那两句话“你们走了,我可怎么活”,拿着那对我们身处城市的人们微不足道的挂面,远去了......

PS: 拍完这组照片后我才知道,5月14号军用运输飞机第一次给汶川空投救援物资就掉在牛脑寨,受灾的村民们没有占为己有,而是汗流浃背地走了两个小时背到山下的县城交给政府。

--------------------------------------------------------------------------------------------------------

对于幸存的灾民来说,最急待解决的显然是温饱问题,救灾部队一边在组织人员全力打通交通,一边在组织采购粮食。现在假设下拨了一定数量的救灾经费要去市场采购大米(散装)。如果市场有m种大米,各种大米的单价和重量已知,请问,为了满足更多灾民的需求,最多能采购多少重量的大米呢?

Input

输入数据首先包含一个正整数C,表示有C组测试用例,每组测试用例的第一行是两个整数n和m(0 < n <= 1000, 0 < m <= 1000 ),分别表示经费的金额和大米的种类,然后是m行数据,每行包含2个整数p和h(1 <= p <= 25,1 <= h <= 100),分别表示单价和对应大米的重量。

Output

对于每组测试数据,请输出能够购买大米的最多重量(你可以假设经费买不光所有的大米)。

每个实例的输出占一行,保留2位小数。

Sample Input

1
7 2
3 3
4 4

Sample Output

2.33

Reference Code

#include<stdio.h>
struct
{
    int p;
    int h;
}rice[1001],t;
int main()
{
    int c,n,m,i,j;
    scanf("%d",&c);
    while (c--)
    {
        double w=0;
        scanf("%d %d",&n,&m);
        for (i=0;i<m;i++)
        {
            scanf("%d %d",&rice[i].p,&rice[i].h);
        }
        for (i=0;i<m-1;i++)
        {
            for (j=0;j<m-i-1;j++)
            {
                if (rice[j].p>rice[j+1].p)
                {
                    t=rice[j];
                    rice[j]=rice[j+1];
                    rice[j+1]=t;
                }
            }
        }
        for (i=0;i<m;i++)
        {
            if (n>=rice[i].p*rice[i].h)
            {
                w+=rice[i].h;
                n-=rice[i].h*rice[i].p;
            }
            else
            {
                w+=(double)n/rice[i].p;
                break;
            }
        }
        printf("%.2lf\n",w);
    }
    return 0;
}

懒虫小鑫

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小鑫是个大懒虫,但是这一天妈妈要小鑫去山上搬些矿石去城里卖以补贴家用。小鑫十分的不开心。不开心归不开心,小鑫还是要做这件事情的。

我们把这个事情简化一下。有n块矿石,设第i块矿石由两个数字wi和pi表示。分别表示这块石头的重量和可以卖的价钱。小鑫每次只能搬一块矿石去城里卖,所以他决定每次都会搬重量最小的那块。如果恰好有几块重量相等,那就在这几块中挑选价值最高的带走。

由于路程原因。小鑫每天只能打m个来回,也就意味着他只能卖掉m块矿石。你能计算出他能得到多少钱么?

Input

输入数据有多组,到文件结束。

对于每一组数据,第一行为n,m。m≤n≤10000。

接下来有n行,每行两个数代表石头的w与p。

Output

对于每组数据,输出有一行为一个数,为答案。

Sample Input

4 2
1 2
1 3
2 2
3 4

Sample Output

5

Reference Code

#include<stdio.h>
struct
{
    int wi;
    int pi;
}stone[10001],t;

/*更为高效的算法,并不是在根据矿石的重量进行排序后再根据相同重量,价值大的再排在前面,而是经过判断后进行一次排序,节省了时间。*/
void qsort(int n)
{
    int i,j,flag;
    for (i=0;i<n-1;i++)
    {
        flag=i;
        for (j=i+1;j<n;j++)
        {
            if (stone[j].wi<stone[flag].wi) flag=j;
            else if (stone[j].wi==stone[flag].wi&&stone[j].pi>stone[flag].pi) flag=j;
        }
        if (flag!=i)
        {
            t=stone[i];
            stone[i]=stone[flag];
            stone[flag]=t;
        }
    }
}

int main()
{
    int n,m,i;
    while (~scanf("%d %d",&n,&m))
    {
        int num=0;
        for (i=0;i<n;i++)
        {
            scanf("%d %d",&stone[i].wi,&stone[i].pi);
        }
        qsort(n);
        for (i=0;i<m;i++)
        {
            num+=stone[i].pi;
        }
        printf("%d\n",num);
    }
    return 0;
}

商人的诀窍

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

E_star和von是中国赫赫有名的两位商人,俗话说的好无商不奸,最近E_star需要进一批苹果。可是他需要的苹果只有von才有,von的苹果都存在他的传说中很牛叉的仓库里,每个仓库都存了不同种类的苹果,而且每个仓库里的苹果的价钱不同。如果E_star想要买仓库i里的所有重量为f[i]的苹果他必须付m[i]的金钱。E_star开着他的传说中的毛驴车去拉苹果,而且他只带了N些金钱。E_star作为传说中的奸商希望用它所带的N金钱得到重量最多的苹果。你作为他最好的朋友,所以他向你求出帮助。希望你能帮忙计算出他能买到最多的苹果(这里指重量最大)。并输出最大重量。

提示:这里仅考虑仓库里苹果的重量,不考虑个数。

Input

第一行包括两个非负整数N,M(分别代表E_star带的金币数,von盛苹果的仓库数量,不超过50)。

接下来有有M行,每行包括两个数非负整数f[i]和m[i]分别表示第i仓库里存有重量为f[i]的苹果,如果将所有苹果买下要花费m[i]的金钱,E_star不必非要将每个仓库的苹果全部买下。

当M,N二者中任一为-1时结束。

Output

E_star用N的金币所能买到的最大重量的苹果的重量。结果保留三位小数。

Sample Input

5 3
7 2
4 3
5 2
20 3
25 18
24 15
15 10
-1 -1

Sample Output

13.333
31.500

Rrefrence Code

#include<stdio.h>
struct qaq
{
    int f,m;
    double b;
}a[10000],key;
void qsort(struct qaq a[],int l,int r)//将结构体做参数传入,进行快排
{
    int i=l,j=r;
    key=a[l];
    if (l>=r) return;
    while (i<j)
    {
        while(i<j&&a[j].b>=key.b) j--;
        a[i]=a[j];
        while(i<j&&a[i].b<=key.b) i++;
        a[j]=a[i];
    }
    a[i]=key;
    qsort(a,l,i-1);
    qsort(a,i+1,r);
}

int main()
{
    int m, n, i;
    double x;
    while(scanf("%d %d",&n,&m)&&m!=-1&&n!=-1)
    {
       x=0;
       for(i=0;i<m;i++)
       {
           scanf("%d %d",&a[i].f,&a[i].m);
       }
       for(i=0;i<m;i++)
       {
            a[i].b=1.0*a[i].m/a[i].f;
       }
       qsort(a,0,m-1);
       for(i =0;i<m;i++)
       {
           if(n>=a[i].m)
           {
               x+=a[i].f;
               n-=a[i].m;
           }
           else
           {
               x+=1.0*n/a[i].b;
               break;
           }
       }
       printf("%.3lf\n",x);
    }
    return 0;
}


递归的函数

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定一个函数 f(a, b, c):

如果 a ≤ 0 或 b ≤ 0 或 c ≤ 0 返回值为 1;

如果 a > 20 或 b > 20 或 c > 20 返回值为 f(20, 20, 20);

如果 a < b 并且 b < c 返回 f(a, b, c−1) + f(a, b−1, c−1) − f(a, b−1, c);

其它情况返回 f(a−1, b, c) + f(a−1, b−1, c) + f(a−1, b, c−1) − f(a-1, b-1, c-1)。

看起来简单的一个函数?你能做对吗?

Input

输入包含多组测试数据,对于每组测试数据:

输入只有一行为 3 个整数a, b, c(a, b, c < 30)。

Output

对于每组测试数据,输出函数的计算结果。

Sample Input

1 1 1
2 2 2

Sample Output

2
4

Reference Code

#include<stdio.h>
int d[21][21][21]={0};

int f(int a,int b,int c)
{
    if (a<=0||b<=0||c<=0) return 1;
    else if (a>20||b>20||c>20) return f(20,20,20);
    else if (d[a][b][c]) return d[a][b][c];
    else if (a<b&&b<c) return d[a][b][c]=f(a,b,c-1)+f(a,b-1,c-1)-f(a,b-1,c);
    else return d[a][b][c]=f(a-1,b,c)+f(a-1,b-1,c)+f(a-1,b,c-1)-f(a-1,b-1,c-1);
}

int main()
{
    int a,b,c,ans;
    while (~scanf("%d %d %d",&a,&b,&c))
    {
        ans=f(a,b,c);
        printf("%d\n",ans);
    }
    return 0;
}

数字三角形问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。
img
对于给定的由n行数字组成的数字三角形,计算从三角形的顶至底的路径经过的数字和的最大值。

Input

输入数据的第1行是数字三角形的行数n,1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。

Output

输出数据只有一个整数,表示计算出的最大值。

Sample Input

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Sample Output

30

Reference Code

#include<stdio.h>
int main()
{
    int n,i,j,a[101][101];
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=i;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    for (i=n;i>=1;i--)
    {
        for (j=1;j<=i;j++)
        {
            if (a[i][j]>a[i][j+1]) a[i-1][j]+=a[i][j];
            else a[i-1][j]+=a[i][j+1];
        }
    }
    printf("%d\n",a[1][1]);
    return 0;
}

最长公共子序列问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定两个序列 X={x1,x2,…,xm} 和 Y={y1,y2,…,yn},找出X和Y的最长公共子序列。

Input

输入数据有多组,每组有两行 ,每行为一个长度不超过500的字符串(输入全是大写英文字母(A,Z)),表示序列X和Y。

Output

每组输出一行,表示所求得的最长公共子序列的长度,若不存在公共子序列,则输出0。

Sample Input

ABCBDAB
BDCABA

Sample Output

4

Reference Code

#include<stdio.h>
#include<string.h>
int main()
{
    int i,j,len1,len2;
    char x[501],y[501];
    while (~scanf("%s %s",x,y))
    {
        int c[501][501]={0};
        len1=strlen(x);
        len2=strlen(y);
        for (i=1;i<=len1;i++)
        {
            for (j=1;j<=len2;j++)
            {
                if (x[i-1]==y[j-1]) c[i][j]=c[i-1][j-1]+1;
                else if (c[i-1][j]>c[i][j-1]) c[i][j]=c[i-1][j];
                else c[i][j]=c[i][j-1];
            }
        }
        printf("%d\n",c[len1][len2]);
    }
    return 0;
}

最长上升子序列

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

一个数的序列bi,当b1 < b2 < ... < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN),我们可以得到一些上升的子序列(ai1, ai2, ..., aiK),这里1<= i1 < i2 < ... < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8)。

你的任务,就是对于给定的序列,求出最长上升子序列的长度。

Input

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。

Output

最长上升子序列的长度。

Sample Input

7
1 7 3 5 9 4 8

Sample Output

4

Reference Code

#include<stdio.h>
int main()
{
    int n,m,i,j,b[1002],len[1002]={0},maxlen=-1;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);
    }
    len[1]=1;
    for (i=2;i<=n;i++)
    {
        m=0;
        for (j=1;j<i;j++)
        {
            if (b[i]>b[j])
            {
                if (m<len[j]) m=len[j];
            }
        }
        len[i]=m+1;
    }
    for (i=1;i<=n;i++)
    {
        if (maxlen<len[i]) maxlen=len[i];
    }
    printf("%d\n",maxlen);
    return 0;
}
Tags:none
上一篇
下一篇