百练C++测试:六题简析

百练C++测试:六题简析

[malicTOC]

A:找和最接近但不超过K的两个元素

序列a中有N个整数,从中找出两个数,使两数之和最接近K但不超过K。\( (1<N<1000,0 \le K \le2000,0 \le a_i \le 1000) \), 输出数据为最接近但不超过K的 两数之和。

此题数据量很小,遍历数组的所有两数之和即可。时间复杂度主要在排序上,为\( O(N^2 \log(N)) \)

#include <cstdio>
#include <algorithm>
using std::sort;
using std::binary_search;
int main(void)
{
    int i,N,K;
    int *a,*p;
    scanf("%d",&N);
    a=new int [N];
    p=new int [N*(N-1)];
    scanf("%d",&K);
    for(i=0;i<N;i++)
    {
        scanf("%d",a+i);
    }
    int idx=0;
    for(i=0;i<N;i++)
    {
        for(int j=i+1;j<N;j++)
        {
            p[idx++]=a[i]+a[j];
        }
    }
    sort(p,p+idx);
    for(i=0;i<K;i++)
    {
        if(binary_search(p,p+idx,K-i))
        {
            printf("%d\n",K-i);
            break;
        }
    }
    return 0;
}

B:附近编号最大的城市

有N座城市编号为1到N,给出N座城市之间的直接距离,在所有与城市1到距离不超过K的城市中,输出编号最大的城市

单源最短路,可以用Dijkstra算法也可以用Folyd算法,本题不需要保存路径所以用Folyd简便一点。求出城市1到所有城市的最短距离,然后从城市编号N倒序遍历,若有城市的最短距离小于K则输出这个城市编号并结束程序。

#include <cstdio>
#include <algorithm>
using std::min;
#define MAXN 12
int N,K;
int edge[MAXN][MAXN];
int main(void)
{
    scanf("%d",&N);
    scanf("%d",&K);
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            scanf("%d",&(edge[i][j]));
        }
    }
    for(int t =0;t<N;t++)
    {
        for(int i=1;i<N;i++)
        {
            edge[0][i] = min(edge[0][i],edge[0][t]+edge[t][i]);
        }
    }
    int i;
    for(i=N-1;i>=0;i--)
    {
        if(edge[0][i]<=K)
        {
            break;
        }
    }
    printf("%d\n",i+1);
    return 0;
}

C:硬币问题

有N种硬币,每种硬币的数量不限。已知各硬币的重量w和面值p,在总重量不超过C的情况下,计算最大可能的金额。\( (N\le 100, C \le 1000,0<w, p \le100) \)

此题用贪心算法:计算已知硬币的”金额/重量”之比。把金额重量比最高者尽量多地利用,若剩下的重量不足以再取得,就从不大于剩余重量的硬币中尽量多的利用金额重量比最高的,直至没有硬币可用。

#include <cstdio>
#include <algorithm>
using std::sort;
struct cNode
{
    int w,p;
    double r;
    bool operator<(const cNode o)
    {
        return r<o.r;
    }
};
int main(void)
{
    int N,R,i;
    int *a;
    cNode *coins;
    scanf("%d",&N);
    scanf("%d",&R);
    coins = new cNode [N];
    a = new int [N];
    for(int i=0;i<N;i++)
    {
        scanf("%d",a+i);
    }
    for(int i=0;i<N;i++)
    {
        coins[i].w = a[i];
        scanf("%d",&(coins[i].p));
        coins[i].r = coins[i].w * 1.0/coins[i].p;
    }
    sort(coins,coins+N);
    int sumPrice = 0;
    for(i=0;i<N;i++)
    {
        sumPrice += (R/coins[i].w) * coins[i].p;
        R = R % coins[i].w;
    }
    printf("%d\n",sumPrice);
    return 0;
}

D:制作蛋糕

制作一个香蕉蛋糕需要2个单位的香蕉,250个单位的面粉,75个单位的糖,100个单位的黄油。
制作一个巧克力蛋糕需要75个单位的可可粉,200个单位的面粉,150个单位的糖,150个单位的黄油。
一个香蕉蛋糕可以卖出400元,
一个巧克力蛋糕可以卖出450元。
为了避免蛋糕变质,每种蛋糕至多只能制作100个。 已知每种原料的数量, 计算利用这些原料最多可以卖多少钱。

此题流程复杂但算法容易,整理好逻辑再写程序。一种方案是:先把所有原料用来做香蕉蛋糕,看看最多能做多少,再看剩下的原料能做多少巧克力蛋糕。由于巧克力蛋糕比香蕉蛋糕卖得贵,就反复试验:少做一个香蕉蛋糕余下来的原料能否做成巧克力蛋糕,若能就把香蕉蛋糕换成巧克力蛋糕,若不能则就按照这个香蕉蛋糕和巧克力蛋糕的数量进行售卖。稍复杂的情况是若原料能做超过100个香蕉蛋糕,则尝试做巧克力蛋糕之后要再检查能否做成香蕉蛋糕,不然可能原料是够做100个香蕉蛋糕的实际却因为换成了巧克力蛋糕而少做了。

#include <cstdio>
#include <algorithm>
using std::min;
int banana,flour,sugar,butter,choc;
int howManyBananaCakeToMake()
{
    int v = min(banana/2,flour/250);
    v=min(v,sugar/75);
    v=min(v,butter/100);
    return v;
}
int howManyChocCakeToMake()
{
    int v = min(choc/75,flour/250);
    v=min(v,sugar/150);
    v=min(v,butter/150);
    return v;
}
void makeBananaCake(int c)
{
    banana -= 2*c;
    flour -= 250 *c;
    sugar -=75*c;
    butter -=100*c;
}
void makeChockCake(int c)
{
    choc -= 75*c;
    flour -= 250*c;
    sugar -= 150*c;
    butter -= 150*c;
}
int main(void)
{
    scanf("%d",&flour);
    scanf("%d",&banana);
    scanf("%d",&sugar);
    scanf("%d",&butter);
    scanf("%d",&choc);
    int num_bananas,num_choc;
    num_bananas = howManyBananaCakeToMake();
    if(num_bananas>100)
    {
        makeBananaCake(100);
        num_bananas=100;
        num_choc = howManyChocCakeToMake();
        if(num_choc>=100)
        {
            printf("%d\n100\n100\n",100*400+100*450);
            return 0;
        }
        while(1)
        {
            makeBananaCake(-1);
            if(howManyBananaCakeToMake()==0)
            {
                break;
            }
            num_bananas-=1;
            makeChockCake(1);
            num_choc+=1;
            if(howManyBananaCakeToMake()==1)
            {
                makeBananaCake(1);
                num_bananas+=1;
            }
        }
        printf("%d\n",num_bananas*400+num_choc*450);
        printf("%d\n%d\n",num_bananas,num_choc);
    }
    else
    {
        makeBananaCake(num_bananas);
        num_choc = howManyChocCakeToMake();
        makeChockCake(num_choc);
        while(1)
        {
            makeBananaCake(-1);
            if(howManyChocCakeToMake()==0)
            {
                break;
            }
            makeChockCake(1);
            num_bananas-=1;
            num_choc+=1;
        }
        printf("%d\n",num_bananas*400+num_choc*450);
        printf("%d\n%d\n",num_bananas,num_choc);
    }
    return 0;
}

E:最短路

N座城市编号从1到N,已知所有城市间的直线距离,求1号城市到N号城市的最短路程。输出途经的城市编号。

单源最短路径并且要输出路径,用Dijkstra算法。

#include <cstdio>
#define MAXN 12
int N;
int dist[MAXN],path[MAXN],S[MAXN];
int G[MAXN][MAXN];
void dijkstra(int v0)
{
    int i,j,k;
    for(i=0;i<N;i++)
    {
        dist[i]=G[v0][i];
        S[i]=0;
        if(i!=v0)
        {
            path[i] = v0;
        }
        else
        {
            path[i] = -1;
        }
    }
    S[v0] = 1;
    dist[v0]=0;
    for(i=0;i<N-1;i++)
    {
        int minVal = 0x7FFFFFF,u=v0;
        for(j=0;j<N;j++)
        {
            if(!S[j] && dist[j]<minVal)
            {
                u=j;
                minVal = dist[j];
            }
        }
        S[u] = 1;
        for(k=0;k<N;k++)
        {
            if(!S[k] && dist[u]+G[u][k] < dist[k])
            {
                dist[k] = dist[u] + G[u][k];
                path[k] = u;
            }
        }
    }
}
int main(void)
{
    int i,j;
    scanf("%d",&N);
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++)
        {
            scanf("%d",&G[i][j]);
        }
    }
    dijkstra(0);
    int shortest[MAXN];
    int k = 0;
    shortest[k] = N-1;
    while(path[shortest[k]]!=0)
    {
        k++;
        shortest[k] = path [shortest[k-1] ];
    }
    k++;
    shortest[k]=0;
    printf("%d\n",dist[N-1]);
    for(j=k;j>0;j--)
    {
        printf("%d ",1+shortest[j]);
    }
    printf("%d\n",1+shortest[0]);
    return 0;
}

F:木材切割

一根长度为N的木材切成M段,每段都是整数。长度为L的一段木材售价为P[L]。给出所有的P[],试计算一种切割方案,使这一根木头的售价最高。

搜索

#include <cstdio>
#include <algorithm>
using std::max;
#define MAXN 102
int comb[MAXN];
int ppc[MAXN];
int profits=0;
int N,M;
void genComb(int n,int m)
{
    if(n<1)
        return ;
    if(m==2)
    {
        for(int i=1;i<n;i++)
        {
            comb[0]=i;
            comb[1]=n-i;
        }
        int S=0;
        for(int k=0;k<M;k++)
        {
            S += ppc[comb[k]];
        }
        profits = max(profits,S);
        return ;
    }
    for(int i = 1;i<=n-m;i++)
    {
        comb[m-1] = i;
        genComb(n-i,m-1);
    }
}
int main(void)
{
    int n,m;
    scanf("%d",&N);
    scanf("%d",&M);
    for(int k=1;k<=N;k++)
    {
        scanf("%d",ppc+k);
    }
    n=N;
    m=M;
    profits = 0;
    genComb(n,m);
    printf("%d\n",profits);
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注