文章

3

粉丝

10

获赞

3

访问

373

头像
表面积 题解:
P1882 华东师范大学2020年机试
发布于2025年4月23日 20:36
阅读数 104

根据此题可得出k个圆柱的最大可视面积为 (k个圆柱的侧面积之和+ k个圆柱中最大的一个圆柱的底面积 ),因此我们可以把圆柱数组按照侧面积降序排列,这样的话前k个圆柱的侧面积总和是最大的,此时可分为两种情况:

①把前k个圆柱的侧面积累加,再加上前k个之中最大的一个底面积,得到ans1;

②有的时候第一种情况不一定正确,因为可能存在一个底面积很大,但是侧面积排在k个圆柱之后的圆柱被忽略掉,如果把这一个圆柱替换掉第一种情况的其中一个圆柱,所得的结果可能更大。由于第一种情况已经计算了前k个圆柱中底面积最大(记为maxBS1)的圆柱,因此在第二种情况我们需要枚举后n-k个底面积比maxBS1更大的圆柱,求得其中最大的(侧面积+底面积)(记为temp),让temp与前k-1个圆柱的侧面积总和相加得到ans2。

最后再取ans1与ans2之间的较大值。

#include<bits/stdc++.h>
using namespace std;
struct Cylinder { 
    long long r, h; 
};
bool cmp(Cylinder c1, Cylinder c2) {
    return c1.r * c1.h > c2.r * c2.h;
}
int main() {
    int n, k;
    cin >> n >> k;
    vector<Cylinder> cs(n);
    for (int i = 0; i < n; i++)
        cin >> cs[i].r >> cs[i].h;
    sort(cs.begin(), cs.end(), cmp);
    long long ans1 = 0, maxBS1 = 0;
    for (int i = 0; i < k; i++) {
        ans1 += cs[i].r * cs[i].h * 2;
        if (maxBS1 < cs[i].r * cs[i].r)
            maxBS1 = cs[i].r * cs[i].r;
    }
 ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发