Intel Code Challenge Elimination Round (Div.1 + Div.2, combined) D. Generating Sets __ dfs+优先队列+贪心

My Solution

dfs+优先队列+贪心

向把数读入到priority_queue，同时用 map<int, bool> mp来标记这些数字，出现过。

然后每次贪心的取最大的值，u = pq.top(), mp[u] = false; 然后dfs的向下推可行的一步，比如 13 到 6 如果可以就标记并返回，否者继续向下找。

如果最大值已经不能向下推了，则pq里维护着的元素就是答案了。

此外，这个方法对于 n == 1时要特殊处理，不然n == 1的时候一直mp[1] = false,然后dfs(1)，这样每次flag都被标记跳不出循环了

总复杂度 O(nlognlogn)

#include 
#include 
#include 



#include 
using namespace std;
typedef long long LL;
const int maxn = 5e5 + 8;

int v;
map<int, bool> mp;
priority_queue pq;
bool flag;
/*//一次性放好不大行，会出问题，比如样例3，
//还是用pq来维护每次把最大的向下推一次，
void dfs(LL x, int i)
{
    if(x == 1){
        if(mp[x] == false){
            mp[x] = true;
            v[i] = x;
            flag = true;
        }
        return;
    }
    if(x & 1){
            dfs((x - 1) / 2, i);
            if(!flag){
                if(mp[x] == false){
                    mp[x] = true;
                    v[i] = x;
                    flag = true;
                }
            }
            return;
    }
    else{
            dfs(x / 2, i);
            if(!flag){
                if(mp[x] == false){
                    mp[x] = true;
                    v[i] = x;
                    flag = true;
                }
                return;
            }
    }
    //......
    if(!flag){
        mp[x] = true;
        v[i] = x;
    }

}
*/
//用priority_queue 来维护， 每次取最大值， 向下推一步，
//然后重新取最大值， 这样一步一步的往下推
//直到最大值不能向下推，得到答案， 因为要求最大值尽可能小， 所以对其它值不做要求
//总的复杂度依然是 O(nlogn);
inline void dfs(int x)
{
    if(x == 1){
        if(mp[x] == false){
            mp[x] = true;
            v = x;
            flag = true;
        }
        return;
    }
    if(x & 1){
        if(mp[(x - 1) / 2] == false){
            mp[(x - 1) / 2] = true;
            v = (x - 1) / 2;
            flag = true;
            return;
        }
        dfs((x - 1) / 2);
    }
    else{
        if(mp[x / 2] == false){
            mp[x / 2] = true;
            v = x / 2;
            flag = true;
            return;
        }
        dfs(x / 2);
    }
    //......

}

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

    int n, u;
    cin >> n;
    for(int i = 0; i < n; i++){ cin >> v;
        mp[v] = true;
        pq.push(v);
    }
    if(n == 1){ cout << 1 << endl; return 0;}  //!

    while(true){
        u = pq.top();
        pq.pop();
        mp[u] = false;
        flag = false;
        //cout << v[i] << " ";
        dfs(u);
        if(!flag) {pq.push(u); break;}
        pq.push(v);
        //cout << v[i]<<endl;
    }

    cout << pq.top(); pq.pop();
    while(!pq.empty()){
        cout << " " << pq.top();
        pq.pop();
    }
    cout << endl;


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

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

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

Intel Code Challenge Elimination Round (Div.1 + Div.2, combined) D. Generating Sets __ dfs+优先队列+贪心

相关推荐

Codeforces Round #403 (Div. 2) C. Andryusha and Colored Balloons DFS

Codeforces Round #345 (Div. 2) D. Image Preview __ two pointers and pretreat

Codeforces Round #375 (Div. 2) D. Lakes in Berland __ dfs+贪心+小根堆

UESTC 2016 Summer Training #1 Div.2 L – Plus or Minus (A) dfs

共有 0 条评论

公告

游戏服务器开发 最新文章

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

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

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

公众号

推荐系统开发 最新文章

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

2从零搭建NB特征平台

3NB特征分类标准

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

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

标签云

栏目分类