SGU 178.Chain

Solution:

一开始做的时候，以为可以将一条长度为n的链分成和n为的任意长度的3部分。结果第二组就Wa了

后来参考了题解，发现是将长度为n的链分成长度为1，x，n-1-x的三条链。再看看题目，不知道是不是自己理解的问题，觉得题目并没有明确说明这一点，仅凭一个n=5，拆成1,1,3 的例子没有体会到这个o(╯□╰)o

不管怎么样，题意是长度为n的链分成长度为1，x，n-1-x的三条链的话，也是很简单的

假设分了k次，那么就会有k个1，和k+1个长度不等的链，k个1，可以组成1~k k个数，那么最长的 k+1条链中最短的链的长度是k+1

这个时候 1~k*2+1 都可以得到，最长的次短的链是k*2+2=2（k+1）

以此类推，第k+1条链的长度应该为（k+1）*2^(k+1)

那么这2k+1条链就可以组成1~k+(k+1)*（2^（k+1）-1）这些数

如果n在这个范围内，那么这是一种可行的方法，现在只要从1开始枚举k的大小，直到n在可组成的数的范围内即可

code

#include <iostream>

using namespace std;

long long n,s,ans,t=1;

int main(){

       cin>>n;

       for(int i=0;;i++){

              if(i+(i+1LL)*((1LL<<i+1)-1)>=n) {

                            cout<<i;

                            return 0;

              }

       }

       return 0;

}

巴特西

SGU 178.Chain

最新文章

热门文章