题目

思路

代码

法一:

#include<stdio.h>
#include<stdlib.h>

typedef struct{long long r;long long h;long long rh;}Data;

int cmp(const void *a,const void *b)       //rh从大到小排 
{
    Data *m=(Data*)a;
    Data *n=(Data*)b;
    return m->rh>n->rh?-1:1;
}

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    Data tab[n];
    for(int i=0;i<n;i++)
    {
           scanf("%lld %lld",&tab[i].r,&tab[i].h);
        tab[i].rh=tab[i].r*tab[i].h;
    }
    qsort(tab,n,sizeof(Data),cmp);
    long long max_r=0;   //找到前m个中最大的r
    long long min_rh=tab[m-1].rh;   //前m个中最小的rh
    long long S=0;
    for(int i=0;i<m;i++)  //选出前m个中的最大半径作为底
    {
        S+=2*tab[i].rh;
        if(tab[i].r>max_r)
        {
            max_r=tab[i].r;
        }
    }
    S+=max_r*max_r;
    for(int i=m;i<n;i++)
    {
        if(tab[i].r>=max_r&&tab[i].r*tab[i].r-max_r*max_r+2*tab[i].rh-2*min_rh>0)  //作底
        {
            S+=tab[i].r*tab[i].r-max_r*max_r+2*tab[i].rh-2*min_rh;
            max_r=tab[i].r;    //更新最大r
            min_rh=tab[i].rh;   //更新最小rh
        }
    }
    printf("%lld",S);
    return 0;
}


法二：

#include<stdio.h>
#include<stdlib.h>

typedef struct{long long r;long long h;long long rh;}Data;

int cmp1(const void *a,const void *b)       //rh从大到小排 
{
    Data *m=(Data*)a;
    Data *n=(Data*)b;
    return m->rh>n->rh?-1:1;
}

int cmp2(const void *a,const void *b)       //S从大到小排 
{
    long long *m=(long long*)a;
    long long *n=(long long*)b;
    return *m>*n?-1:1;
}

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    Data tab[n];
    for(int i=0;i<n;i++)
    {
           scanf("%lld %lld",&tab[i].r,&tab[i].h);
        tab[i].rh=tab[i].r*tab[i].h;
    }
    qsort(tab,n,sizeof(Data),cmp1);
    long long S[n];
    for(int i=0;i<n;i++)   //有的编译器不支持对用变量定义长度的数组直接初始化
    {
        S[i]=0;
    }
    for(int i=0;i<n;i++)  
    {
        S[i]+=tab[i].r*tab[i].r+2*tab[i].rh;
        int count=1;
        for(int j=0;j<n;j++)
        {
            if(count==m)   
            {
                break;
            }
            if(j!=i&&tab[j].r<=tab[i].r)     
            {
                S[i]+=2*tab[j].rh;
                count++;
            }
        }
    }
       qsort(S,n,sizeof(long long),cmp2);
    printf("%lld",S[0]);
    return 0;
}