CodeForces - Duff and Weight Lifting - #326 (Div. 1)

c++ iostream I/O优化

一句话题意：有若干个数字，都是2的n次幂；每次取出若干个数字，且要保证取出的数字之和也是2的n次幂；问至少要取多少次。

样例输入：

样例输出：

解：

我们从最简单的样例入手。

样例输入可以整理如下。x的后面表示这个数字的出现次数。

2^1 x2

我们发现，两个相同幂次的数，刚好能“等价变换”为更高次的数。

2^1 x2 => 2^2 x1

再加上已有的2^2，总共有2个2^2啦。于是，继续变换，

2^2 x2 => 2^3 x1

再加上已有的2个2^3，就有3个2^3啦。

2^3 x2+1

取出其中两个进行“变换”，最终结果就是

2^3 x1

然后，我们发现不管怎么操作都无法进一步组合两个数进行变换。现在有两个数，所以答案是2。

做到这里，就不难看出其中的规律。二进制下的“进位”而已。

#include 
    
     #include
     
      #include
      
       using namespace std;int orz[1000000+10000];int l[] ={1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576};int search(int n){    for(int i = 0;i<20;i++){        if(l[i+1]>=n){            return i;        }    }    return -1;}int main(){    std::ios::sync_with_stdio(false);      std::cin.tie(0);      int n,t;    scanf("%d", &n);    int step = 0;    int max = 0;    for(int i = 0;i
       
        max?t:max);        orz[t]++;    }    for(int i = 0;i<=max;i++){        if(orz[i] == 0) continue;        int now_cnt = orz[i];        int pow;        while(now_cnt){            if(now_cnt == 1) step++;            now_cnt -= l[pow = log2(now_cnt)];            orz[max=(i+pow>max?i+pow:max),i+pow]++;        }    }    printf("%d\n", step);    return 0;}
       
      
     
    

其中两行，

std::ios::sync_with_stdio(false);  std::cin.tie(0);

就是所谓的iostream优化。

第一行的原理就是解除iostream和stdio的绑定。

第二行的原理是解除cin与cout的绑定。

详情请看。

为啥要优化呢？因为我起初做这题是用的51nod（这个网站提供这题的中文题目）的机器非常辣鸡，就是卡I/O。疯狂TLE。

我试了能AC的两种方法，第一种是删除所有c++特性语句，使用printf与scanf，用c来提交；第二种就是所述的iostream优化。

题外话：

有些时候，自己重写printf和scanf效率更高。

因为getchar和putchar函数很快。

从qscqesze的上摘抄如下：

template
    
      inline T& RD(T &x){      //cin >> x;      //scanf("%d", &x);      char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0';      //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0';      return x;  }    int ____Case; template
     
       inline void OT(const T &x){      //if (x == -1) printf("Case %d: NO\n", ++____Case);      //else printf("Case %d: %d\n", ++____Case, x);      //printf("%I64d\n", x);      //printf("%.2lf\n", x);      printf("%d\n", x);      //cout << x << endl;  }
     
    

这相当于重写了scanf。

至于用putchar重写printf……以后再说吧，因为很少遇到大量输出的情况。