1-1 活动选择

任务描述:

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

输入格式:

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

输出格式:

输出最佳安排序列所包含的各个活动（按照活动被安排的次序，两个活动之间用逗号分隔），如果有多个活动安排序列符合要求输出字典序最小的序列。

输入样例:

输出样例:

1,5,4

答案：

#include <stdio.h>
struct node
{
    int begin;
    int end;
    int digit;
}a[120], b[120];
void sort(struct node a[], int n)
{
    int i, j;
    struct node temp;
    for(i = 0;i < n-1;i++){
        for(j = 0;j < n-1-i;j++){ if(a[j].end > a[j+1].end){
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}
int main()
{
    int n;
    int i;
    scanf("%d", &n);
    for(i = 0;i < n;i++){
        scanf("%d %d", &a[i].begin, &a[i].end);
        a[i].digit = i+1;
    }
    sort(a,n);
    int k = 0;
    for(i = 0;i < n;i++){ if(a[i].begin >= b[k].end){
            k++;
            b[k] = a[i];
        }
    }
    for(i =1;i <= k;i++){
        if(i == 1){
            printf("%d", b[i].digit);
        }else {
            printf(",%d", b[i].digit);
        }
    }
    printf("\n");
    return 0;
}

1-2 删数问题

任务描述:

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

输入格式:

输入两个数字，分别为原始数n，要去掉的数字数s (s < n)；

输出格式:

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

输入样例:

178543 4

输出样例:

答案：

#include <stdio.h>
#include 
int main()
{
    char num[251]={'\0'};
    int s,i,j;
    scanf("%s",num);
    scanf("%d",&s);
    while (s>0)    
    {
           i=0;          
          while (num[i]!='\0' && num[i]<=num[i+1])
                i++;
         for(j=i;j<strlen(num);j++)
               num[j]=num[j+1];  
        s--;
    }
    i=0;
    while(num[i]=='0') i++; 
    if (num[i]=='\0') printf("0\n");
    else  printf("%s\n",&num[i]);
    return 0;
}

1-3 活动选择问题

任务描述:

sdut 大学生艺术中心每天都有n个活动申请举办，但是为了举办更多的活动，必须要放弃一些活动，求出每天最多能举办多少活动。

输入格式:

输入第一行为申请的活动数n(n<100)，从第2行到n+1行，每行两个数，是每个活动的开始时间b，结束时间e；

输出格式:

输出每天最多能举办的活动数。

输入样例:

输出样例:

答案：

#include <stdio.h>
struct node
{
    int begin;
    int end;
    int digit;
}a[120], b[120];
void sort(struct node a[], int n)
{
    int i, j;
    struct node temp;
    for(i = 0;i < n-1;i++){
        for(j = 0;j < n-1-i;j++){ if(a[j].end > a[j+1].end){
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}
int main()
{
    int n;
    int i;
    scanf("%d", &n);
    for(i = 0;i < n;i++){
        scanf("%d %d", &a[i].begin, &a[i].end);
        a[i].digit = i+1;
    }
    sort(a,n);
    int k = 0;
    for(i = 0;i < n;i++){ if(a[i].begin >= b[k].end){
            k++;
            b[k] = a[i];
        }
    }
    printf("%d\n",k);
    return 0;
}

1-4 区间覆盖问题

任务描述:

用i来表示x坐标轴上坐标为[i-1，i]的长度为1的区间，并给出n个不同的整数，表示n个这样的区间。现在要求画m条线段覆盖住所有的区间，条件是：每条线段可以任意长，但是要求所画线段的长度之和最小，并且线段的数目不超过m。

输入格式:

输入包括多组数据，每组数据的第一行表示区间个数n(1≤n≤200) 和所需线段数m(1≤m≤50），第二行表示n个点的坐标i(1≤i≤200）。

输出格式:

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

输入样例:

在这里给出一组输入。例如：

5 3
1 3 8 5 11

输出样例:

在这里给出相应的输出。例如：

答案：

#include <stdio.h>
void sort(int value[], int n);
int main()
{
    int n, i, m;
    int position[210];
    int distance[210];
    while(~scanf("%d%d", &n, &m))
    {
        for(i = 0; i<n; i++)
        {
            scanf("%d", &position[i]);
        }
        sort(position, n);
        for(i = 0; i<n-1; i++) { distance[i] = position[i] - position[i+1]-1; } sort(distance,n-1); if(m>=n)
        {
            printf("%d\n", n);
        }
        else
        {
            int nline = 1;
            int totallength = position[0]-position[n-1]+1;
            int devide = 0;
            while((nline<m)&&(distance[devide]>0))
            {
                nline++;
                totallength-=distance[devide];
                devide++;
            }
            printf("%d\n", totallength);
        }
    }
    return 0;
}
void sort(int value[], int n)
{
    int i, j, t;
    for(i = 0; i<n-1; i++)
    {
        for(j = 0; j<n-1-i; j++)
        {
            if(value[j]<value[j+1])
            {
                t = value[j];
                value[j] = value[j+1];
                value[j+1] = t;
            }
        }
    }
}

1-5 最少拦截系统

任务描述:

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

输入格式:

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

输出格式:

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

输入样例:

在这里给出一组输入。例如：

8 389 207 155 300 299 170 158 65

输出样例:

在这里给出相应的输出。例如：

答案：

#include <stdio.h>
#include 
int main()
{
    int n,i,j,b[100000];
    while(~scanf("%d",&n))
    {
        int h,sum=1;
        memset(b,0,sizeof(b));
        scanf("%d",&b[sum]);
        for(i=2;i<=n;i++)
        {
            scanf("%d",&h);
            for(j=1;j<=sum;j++) { if(b[j]>=h)
                {
                    b[j]=h;
                    break;
                }
            }
            if(j>sum)
            {
                b[++sum]=h;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

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

任务描述:

时间：2008年5月16日（震后第4天）
地点：汶川县牛脑寨
人物：羌族老奶奶

【转载整理】牛脑寨是一个全村600多人的羌族寨子，震后几天，这里依然能常常听到隆隆的声音，那是对面山上石头不断滑落的声音。在完成整个突击队的抢修移动基站的任务后，我提着相机开始记录这里的受创情况。
突然，我的视线里出现一个羌族老人，这让我无比的震惊，要知道，那是一个极陡的坡，这个佝偻着腰的老人是怎么艰难地爬上来的？她上来做什么？老人背后是极陡的坡，她只有一只眼睛有依稀的视力，望着满地废墟，她徘徊了很久。家在哪里，她极力地用很低的视力找寻着。她曾经的家就在旁边，但是满目废墟已经让老人看不出来。她举目远眺，期望那里能看到家的一点点痕迹。原来家就在旁边，左手抓住一个房橼，努力让自己站住，地震过去三天了，她第一次回到曾经的家。一个倒塌的柜子，里面装着一丝希望，老人很吃力地搬动掩盖在柜子上的薪柴。老人找到一把木匠用的刨子，老泪纵横，或许有哪个逝去的亲人是木匠。睹物思人，逝者已矣。继续找，一把散碎的挂面出现在我的眼前。她颤颤巍巍地捞起铺满灰尘的挂面，再次流出了眼泪……看着她仔细地把挂面放进胸前的围腰里，我顿然感觉到，这是老人在得到外援之前赖以生存的口粮了，如果不是交通中断，外部救援进不来，老人家又何必拖着80多岁的躯体，强忍失去亲人的痛苦，重新回到这夺取她亲人生命的废墟，寻找这点点挂面？老人是真饿了……老人佝偻着腰，低声喃喃地念着那两句话“你们走了，我可怎么活”，拿着那对我们身处城市的人们微不足道的挂面，远去了……

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

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

输入格式:

第一行是两个整数n和m（0 < n <= 1000, 0 < m <= 1000 ）,分别表示经费的金额和大米的种类，然后是m行数据，每行包含2个整数p和h(1 <= p <= 25,1 <= h <= 100)，分别表示单价和对应大米的重量。

输出格式:

请输出能够购买大米的最多重量（你可以假设经费买不光所有的大米）。输出占一行，保留2位小数。

输入样例:

在这里给出一组输入。例如：

7 2
3 3
4 4

输出样例:

在这里给出相应的输出。例如：

2.33

答案：

#include <stdio.h>
#include
struct node
{
    int p;
    int h;
    int ph;
}a[1000],abc;
void sort (int m)
{
    int i,j;
    for(i=0;i<m-1;i++)
    {
        for(j=0;j<m-1-i;j++) { if(a[j].p>a[j+1].p)
            {
                abc=a[j];
                a[j]=a[j+1];
                a[j+1]=abc;
            }
        }
    }
}
int main()
{
    int c;
    int n,m;
    int i,j;
    double max=0;
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++) { scanf("%d%d",&a[i].p,&a[i].h); a[i].ph=a[i].p*a[i].h; } sort(m); max=0; for(i=0;n>0&&i<m;i++) { if(n>=a[i].ph)
            {
                n-=a[i].ph;
                max+=a[i].h;
            }
            else
            {
                max+=(1.0*n)/a[i].p;
                n=0;
            }
        }
        printf("%.2lf\n",max);
    return 0;
}

1-7 懒虫小鑫

任务描述:

小鑫是个大懒虫，但是这一天妈妈要小鑫去山上搬些矿石去城里卖以补贴家用。小鑫十分的不开心。不开心归不开心，小鑫还是要做这件事情的。我们把这个事情简化一下。有n块矿石，设第i块矿石由两个数字wi和pi表示。分别表示这块石头的重量和可以卖的价钱。小鑫每次只能搬一块矿石去城里卖，所以他决定每次都会搬重量最小的那块。如果恰好有几块重量相等，那就在这几块中挑选价值最高的带走。由于路程原因。小鑫每天只能打m个来回，也就意味着他只能卖掉m块矿石。你能计算出他能得到多少钱么？

输入格式:

第一行为n，m。m≤n≤10000。接下来有n行，每行两个数代表石头的w与p。

输出格式:

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

输入样例:

在这里给出一组输入。例如：

输出样例:

在这里给出相应的输出。例如：

答案：

#include <stdio.h>
struct node
{
    int w,p;
} s[11234];
void sort(struct node s[], int n)
{
    int i, j, k;
    struct node temp;
    for(i= 0; i < n-1; i++)
    {
        k  =i;
        for(j = i+1; j < n; j++)
        {
            if(s[j].p < s[k].p) { k =j; } else if(s[j].p == s[k].p) { if(s[j].w > s[k].w)
                {
                    k = j;
                }
            }
        }
        if(k != i)
        {
            temp = s[k];
            s[k] = s[i];
            s[i] = temp;
        }
    }
}
int main()
{
    int n, m;
    while(~scanf("%d %d", &n, &m))
    {
        int i;
        for( i = 0; i < n; i++)
        {
            scanf("%d %d", &s[i].p, &s[i].w);
        }
        sort(s,n);
        int sum = 0;
        for(i =0 ; i < m; i++)
        {
            sum += s[i].w;
        }
 
        printf("%d\n", sum);
    }
    return 0;
}

1-8 装船问题

任务描述:

王小二毕业后从事船运规划工作，吉祥号货轮的最大载重量为M吨，有10种货物可以装船。第i种货物有wi吨，总价值是pi。王小二的任务是从10种货物中挑选若干吨上船，在满足货物总重量小于等于M的前提下，运走的货物的价重比最大。

输入格式:

输入数据的第一行有一个正整数M(0 < M < 10000)，表示所有货物最大载重量。在接下来的10行中，每行有若干个数（中间用空格分开），第i行表示的是第i种货物的货物的总价值pi ,总重量wi。(pi是wi的整数倍，0 < pi , wi < 1000)

输出格式:

输出一个整数，表示可以得到的最大价值。

输入样例:

在这里给出一组输入。例如：

输出样例:

在这里给出相应的输出。例如：

答案：

#include <stdio.h>
struct node
{
    int wi;
    int pi;
    int ave;
}a[10],t;
 
int main()
{
    int m;
    int i,j;
    int h = 0;
    scanf("%d",&m);
    for( i = 0; i < 10; i++ )
    {
        scanf("%d%d",&a[i].pi,&a[i].wi);
        a[i].ave = a[i].pi / a[i].wi;
    }
    for( i = 0; i < 9; i++ )
    {
        for( j = 0; j < 9 - i; j++ )
        {
            if( a[j].ave < a[j+1].ave )
            {
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
    }
    for( i = 0; i < 10; i++ )
    {
        if( m < a[i].wi )
        break;
        m -= a[i].wi;
        h += a[i].pi;
    }
    if( i < 10 )
    h += m * a[i].ave;
    printf("%d\n",h);
    return 0;
}

1-9 商人小鑫

任务描述:

小鑫是个商人，当然商人最希望的就是多赚钱，小鑫也一样。这天，他来到了一个遥远的国度。那里有着n件商品，对于第i件商品需要付出ci的价钱才能得到。当然，对于第i件商品，小鑫在自己心中有一个估价pi：代表着当他买下这件商品后带回他的国家可以卖出的价格。小鑫只能带回m件商品，你能帮他计算一下他最多能赚多少钱么？

输入格式:

第一行是n，m。( 0< m ≤ n ≤ 1000000 )紧接着有n行，每一行有两个数 c ，p。第i行代表着ci，pi。( ci ≤ pi, 保证数据都在int范围内 )

输出格式:

输出一行一个数，代表小鑫能赚多少钱。

输入样例:

在这里给出一组输入。例如：

输出样例:

在这里给出相应的输出。例如：

答案：

#include <stdio.h>
#include
struct
{
    int c,p;
} k[10000001],t;
int l[10000001];
void qsort(int left,int right)
{
    int a=l[left],i=left,j=right;
    if(left>right)return ;
    while(i<j)
    {
        while(i<j&&l[j]<=a)j--;
        l[i]=l[j];
        while(i<j&&l[i]>=a)i++;
        l[j]=l[i];
    }
    l[i]=a;
    qsort(left,i-1);
    qsort(i+1,right);
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        int i;
        for(i=0; i<n; i++)
        {
            scanf("%d%d",&k[i].c,&k[i].p);
            l[i]=k[i].p-k[i].c;
        }
        qsort(0,n-1);
        int sum=0;
        for(i=0; i<m; i++)
        {
            sum+=l[i];
        }
        printf("%d\n",sum);
    }
    return 0;
}

1-10 商人的诀窍

任务描述:

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

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

输入格式:

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

输出格式:

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

输入样例:

在这里给出一组输入。例如：

输出样例:

在这里给出相应的输出。例如：

31.500

答案：

#include <stdio.h>
struct node
{
    int w;
    int p;
    double q;
}a[51],t;
int main()
{
    int n,m,i,j,b;
    double sum;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(n==-1||m==-1)return 0;
        sum=0;
        b=0;
       for(i=0;i<m;i++)
       {
           scanf("%d %d",&a[i].w,&a[i].p);
           a[i].q=a[i].p*1.0/a[i].w;
           b=b+a[i].p;
       }
        if(b<=n)
        {
            for(i=0;i<m;i++)
            {
                sum=sum+a[i].w;
            }
        }
        else
        {
            for(i=0;i<m;i++)
            {
                for(j=i+1;j<m;j++) { if(a[i].q>a[j].q)
                    {
                        t=a[i];
                        a[i]=a[j];
                        a[j]=t;
                    }
                }
            }
            for(i=0;i<m;i++)
            {
                if(a[i].p<=n)
                {
                    sum=sum+a[i].w;
                    n=n-a[i].p;
                }
                else
                {
                    sum=sum+(n*1.0/a[i].q);
                    break;
                }
            }
        }
        printf("%.3lf\n",sum);
    }
    return 0;
}

1-1 活动选择

任务描述:

输入格式:

输出格式:

输入样例:

输出样例:

相关限制：

答案：

1-2 删数问题

任务描述:

输入格式:

输出格式:

输入样例:

输出样例:

相关限制：

答案：

1-3 活动选择问题

任务描述:

输入格式:

输出格式:

输入样例:

输出样例:

相关限制：

答案：

1-4 区间覆盖问题

任务描述:

输入格式:

输出格式:

输入样例:

输出样例:

相关限制：

答案：

1-5 最少拦截系统

任务描述:

输入格式:

输出格式:

输入样例:

输出样例:

相关限制：

答案：

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

任务描述:

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

输入格式:

输出格式:

输入样例:

输出样例:

相关限制：

答案：

1-7 懒虫小鑫

任务描述:

输入格式:

输出格式:

输入样例:

输出样例:

相关限制：

答案：

1-8 装船问题

任务描述:

输入格式:

输出格式:

输入样例:

输出样例:

相关限制：

答案：

1-9 商人小鑫

任务描述:

输入格式:

输出格式:

输入样例:

输出样例:

相关限制：

答案：

1-10 商人的诀窍

任务描述:

输入格式:

输出格式:

输入样例:

输出样例:

相关限制：

发送评论编辑评论