Codeforces.GYM101612E.Equal Numbers(贪心)-白红宇

Codeforces.GYM101612E.Equal Numbers(贪心)

阅读量：5112 次

发布时间：2019-06-13

本文共 1136 字，大约阅读时间需要 3 分钟。

\(Description\)

给定\(n\)个数，每次可以将任意一个数乘上任意一个正整数。

求\(k\)次操作后，数列中数的种类最少可以是多少。对每个\(0\leq k\leq n\)输出答案。

\(n\leq 3\times10^5,a_i\leq10^6\)。

\(Solution\)

有两种贪心策略，一是每次找一个出现次数最少的数，把它变成所有数的LCM；二是找一个出现次数最少，且它的某个倍数存在于原数列里的数，将它变成它的这个倍数。

对两种情况取\(\min\)即可。

//93ms  8600KB#include 
    
     #include 
     
      #include 
      
       #include 
       
        //#define gc() getchar()#define MAXIN 300000#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)typedef long long LL;const int N=1e6+3;int tm[N];std::vector
        
          va,vb;char IN[MAXIN],*SS=IN,*TT=IN;inline int read(){    int now=0;register char c=gc();    for(;!isdigit(c);c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now;}int main(){    freopen("equal.in","r",stdin);    freopen("equal.out","w",stdout);    int n=read();    for(int i=1; i<=n; ++i) ++tm[read()];    for(int i=1; i

::iterator pa=va.begin(),pb=vb.begin(); for(int i=0,sa=0,sb=0,a=0,b=0; i<=n; ++i) { while(sa+*pa<=i) sa+=*pa++, ++a; while(sb+*pb<=i) sb+=*pb++, ++b; printf("%d ",tmp-std::max(a-1,b)); } return 0;}

转载于:https://www.cnblogs.com/SovietPower/p/9862478.html

你可能感兴趣的文章

33. Search in Rotated Sorted Array & 81. Search in Rotated Sorted Array II