Codeforces Round #378 (Div. 2) D. Kostya the Sculptor __ data structures、map<ii, priority_queue<ii>>

Source

My Solution

题意：可以把2个长方体合并成1个(只能把尺寸相同的面合并)，或者只选一个，然后搞出一个球，求选1个或者2个合并成1个，从而球的体积最大

data structures、map<ii, priority_queue > mp;

把长方体的分成地面和高来储存，

如果长宽高3条边都不相等，则每个面存一次，mp[ii(x, y)].push(ii(z, i)); mp[ii(y, z)].push(ii(x, i)); mp[ii(x, z)].push(ii(y, i)); 并且确保mp.first.first >= mp.first.second

如果有2条边相等，则存2个面

如果长宽高都相等，则存1个面

存储完后，用迭代器访问一遍map，每个priority_queue，访问前1个和前2个，并用 a, b, ans分别维护选中的第一个长方体的编号、选中的第二个长方体的编号(如果有)、所求球体的直径。

复杂度 O(nlogn)

#include 
#include 
#include 




#include 
using namespace std;
typedef long long LL;
typedef pair<LL, LL> ii;
const int maxn = 1e6 + 8;

map<ii, priority_queue > mp;

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    LL n, x, y, z;
    cin >> n;
    for(int i = 1; i <= n; i++){ cin >> x >> y >> z;
        if(x == y){
            mp[ii(x, y)].push(ii(z, i));
            if(x != z){
                if(x > z) mp[ii(x, z)].push(ii(y, i));
                else mp[ii(z, x)].push(ii(y, i));
            }
        }
        else if(x == z){
            mp[ii(x, z)].push(ii(y, i));
            if(x > y) mp[ii(x, y)].push(ii(z, i));
            else mp[ii(y, x)].push(ii(z, i));
        }
        else if(y == z){
            mp[ii(y, z)].push(ii(x, i));
            if(x > y) mp[ii(x, y)].push(ii(z, i));
            else mp[ii(y, x)].push(ii(z, i));
        }
        else{
            if(x > y) mp[ii(x, y)].push(ii(z, i));
            else mp[ii(y, x)].push(ii(z, i));

            if(x > z) mp[ii(x, z)].push(ii(y, i));
            else mp[ii(z, x)].push(ii(y, i));

            if(y > z) mp[ii(y, z)].push(ii(x, i));
            else mp[ii(z, y)].push(ii(x, i));            //..else mp[ii(y, z)].push(ii(x, i));
        }
    }

    LL a = -1, b = -1, ans = 0, ai, bi, c;
    for(auto i = mp.begin(); i != mp.end(); i++){
        if((i->second).size() >= 1){
            ai = (i->second).top().second, c = (i->second).top().first;
            (i->second).pop();
            if(ans < min((i->first).second, c)){
                ans = min((i->first).second, c);                  //前面写成ans = c 了⊙﹏⊙‖∣
                a = ai;
                b = -1;
            }

            if((i->second).size() >= 1){
                bi = (i->second).top().second, c += (i->second).top().first;
                (i->second).pop();
                if(ans < min((i->first).second, c)){
                    ans = min((i->first).second, c);              //前面写成ans = c 了⊙﹏⊙‖∣
                    a = ai;
                    b = bi;
                }
            }


        }
    }

    if(b == -1){
        cout << 1 << endl;
        cout << a << endl;
    }
    else{
        cout << 2 << endl;
        cout << a << " " << b << endl;
    }

    #ifdef LOCAL
    mp.clear();
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

Codeforces Round #378 (Div. 2) D. Kostya the Sculptor __ data structures、map>

相关推荐

Codeforces Round #400 (Div. 1 + Div. 2, combined) C. Molly’s Chemicals 区间和、构造、前缀的后缀

2016 UESTC Training for Dynamic Programming M – 柱爷抢银行欢庆5.1special 递推

UESTC 1297 Bank 思维题

Codeforces Round #364 (Div. 2) D. As Fast As Possible __ binary search、方程或解方程直接解出答案

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类