首页 > 代码库 > CodeForces 722D Generating Sets

CodeForces 722D Generating Sets

贪心,优先队列。

每次变最大的数,变到最大的能变的一个就停止。如果发现最大的数不能变小,那么输出。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c = getchar();    x = 0;    while(!isdigit(c)) c = getchar();    while(isdigit(c)) { x = x * 10 + c - 0; c = getchar(); }}priority_queue<int>q;map<int,bool>m;int n;int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)    {        int x; scanf("%d",&x);        q.push(x); m[x]=1;    }    while(1)    {        int top=q.top();        while(1)        {            if(top==0) break;            if(m[top]) top=top/2;            else break;        }        if(top==0) break;        q.pop();        m[top]=1;        q.push(top);    }    while(!q.empty())    {        printf("%d ",q.top());        q.pop();    }    return 0;}

 

CodeForces 722D Generating Sets