题解：P13168 [GCJ 2017 #1C] Ample Syrup

zjl2013 · 2025-12-03 21:21:30 · 题解

题意

题目要求出从下往上暴露表面积最大值，可以将其化简为最下方松饼顶面积与各层松饼侧面积之和。

实现

对于每个询问，进行侧面积降序排序，第一层循环枚举最下方的松饼，第二层循环再逐层贪心选择侧面积进行计算。

细节

对于计算，应进行特判，如：第二层循环枚举下标与第一层重复，则跳过；上方松饼比最下方半径大亦跳过。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,m,ans;
const long double pi=3.14159265359;
struct Node{
    ll r,h;
}a[10086];
bool cmp(Node a1,Node a2){
    return a1.r*a1.h>a2.r*a2.h;
}
int main(){
    cin>>t;
    for(ll _=1;_<=t;_++){
        ans=0;
        cin>>n>>m;
        for(ll i=1;i<=n;i++){
            cin>>a[i].r>>a[i].h;
        }
        sort(a+1,a+n+1,cmp);
        for(ll i=1;i<=n;i++){
            ll now=a[i].r*a[i].r+a[i].r*2*a[i].h,k=0;
            for(ll j=1;j<=n&&k<m-1;j++){
                if(j!=i&&a[j].r<=a[i].r){
                    now+=a[j].r*2*a[j].h;
                    k++;
                }
            }
            if(k==m-1) ans=max(ans,now);
        }
        cout<<fixed<<setprecision(9);
        cout<<"Case #"<<_<<": "<<ans*pi<<'\n';
    }
    return 0;
}

总结

一道水黄，但是应注意细节，才能满分。