UESTC 1595 老司机的毒奶 贪心+二叉树+优先队列

老司机的毒奶贪心+二叉树+优先队列

Source

2017 UESTC Training for Data Structures

My Solution

题意：给出n个不同的数，每个数可以最多进行ki次操作，每次操作 ai/2。每次操作后n个数必须互不相等。
求max{ai}(1<=i<=n)的最小值。

贪心+二叉树+优先队列
ai的k次ai/2的操作，刚好像是在二叉树上走，也就是这n个数可以丢到一个二叉树里，每次把编号最大的节点，
往根的方向走，需找一个没有被标记过的节点，找到最近的一个可行节点则本次操作成功，继续处理新的最大值。

故把所有暂时存在的数用map<int, bool> mp标记，且把所有的数丢到优先队列里，
每次取出最大的，判断是否存在k， x = pq.top()>>k，x没有被标记过。
则mp[pq.top()] = false; mp[x] = true;然后pop后把x丢入pq，继续判断新的top。
如果不能继续操作了，则结束循环。
最后留下的pq.top()就是答案了。

#include 
#include 
#include 

#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 8;

map<int, bool> mp;
priority_queue pq;

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

    int n, i, x;
    scanf("%d", &n);
    for(i = 0; i < n; i++){ scanf("%d", &x); mp[x] = true; pq.push(x); } while(!pq.empty()){ x = pq.top(); mp[x] = false; while(x){ x >>= 1;
            if(x && !mp[x]){
                break;
            }
        }
        if(x && !mp[x]){
            pq.pop();
            pq.push(x);
            mp[x] = true;
        }
        else{
            break;
        }
    }
    printf("%dn", pq.top());



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

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

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

UESTC 1595 老司机的毒奶贪心+二叉树+优先队列

老司机的毒奶贪心+二叉树+优先队列

Source

My Solution

相关推荐

2016 ACM/ICPC Asia Regional Dalian Online 1010 Weak Pair 离散化+树状数组

2016 UESTC Training for Data Structures D – 卿学姐与魔法优先队列、构造

Codeforces 620E New Year Tree dfs序+线段树+状态压缩

HDU – 3887 Counting Offspring dfs序+线段树

共有 0 条评论

公告

游戏服务器开发 最新文章

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

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

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

公众号

推荐系统开发 最新文章

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

2从零搭建NB特征平台

3NB特征分类标准

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

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

标签云

栏目分类

UESTC 1595 老司机的毒奶 贪心+二叉树+优先队列

老司机的毒奶 贪心+二叉树+优先队列

Source

My Solution

相关推荐

2016 ACM/ICPC Asia Regional Dalian Online 1010 Weak Pair 离散化+树状数组

2016 UESTC Training for Data Structures D – 卿学姐与魔法 优先队列、构造

Codeforces 620E New Year Tree dfs序+线段树+状态压缩

HDU – 3887 Counting Offspring dfs序+线段树

共有 0 条评论

公告

游戏服务器开发最新文章

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

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

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

公众号

推荐系统开发最新文章

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

2从零搭建NB特征平台

3NB特征分类标准

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

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

标签云

栏目分类

UESTC 1595 老司机的毒奶贪心+二叉树+优先队列

老司机的毒奶贪心+二叉树+优先队列

2016 UESTC Training for Data Structures D – 卿学姐与魔法优先队列、构造