題目

思路

代碼

法一:

#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個(gè)中最大的r
????long?long?min_rh=tab[m-1].rh;???//前m個(gè)中最小的rh
????long?long?S=0;
????for(int?i=0;i<m;i++)??//選出前m個(gè)中的最大半徑作為底
????{
????????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++)???//有的編譯器不支持對(duì)用變量定義長(zhǎng)度的數(shù)組直接初始化
????{
????????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;
}