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

CodeForces 722D Generating Sets

2024-08-15 11:39:07   218人阅读

　　题意：如果你有一个原数列的话你可以对任何一个数字进行操作，令这个数字乘2或者乘2后在加1。现在给你一个目标数列，让你求一个原数列，这个原数列是所有可能的原数列当中最大的一个元素最小的那种。注意原数列和目标数列都必须满足set内元素的性质（即每个元素都不相同），但是在变化的过程中不需要满足这个条件。

　　分析：原来的贪心思路是每次取出最大的一个元素把它一直除以2，一直这样操作到不能再小为止（再小就重复了），这样操作完每个数字以后就可以了。但是这样的话连最后一组数据都过不了。于是稍稍的改变贪心思路，每次取出最大的数字，除以2，如果没有重复元素的话就结束（也就是说不必一次就把它除到最小）并且放回集合里面，一直这样操作直到最大的数字无法变化为止。这样的贪心思路才是正确的。

　　具体见代码：

 1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <set> 5 using namespace std; 6 const int N = 50000 + 50; 7  8 int a[N],n; 9 10 int main()11 {12     set<int> S;13     scanf("%d",&n);14     for(int i=1;i<=n;i++) {scanf("%d",a+i);S.insert(a[i]);}15     16     while(1)17     {18         set<int>::iterator it = S.end();19         it--;20         int p = *it;21         while(S.find(p)!=S.end() && p)22         {23             p >>= 1;24         }25         if(p==0) break;26         S.erase(it);27         S.insert(p);28     }29     int first = 0;30     for(set<int>::iterator it=S.begin();it!=S.end();it++)31     {32         if(!first) {first=1;printf("%d",*it);}33         else printf(" %d",*it);34     }35     puts("");36 }

 

CodeForces 722D Generating Sets


联系
我们