【hihocoder 1650】扁平化管理

描述

小Hi的公司包括CEO在内一共有N名员工。这N名员工的上下级关系形成树形结构，CEO处于树根，普通员工处于叶子节点。  

现在公司希望管理扁平化，要求树形结构中的层级不超过L层。此外，假设A是B的直接上级，那么B管理的下属数目必须少于A管理的下属数目。  

请你判断CEO至少要管理多少名下属？

例如N=12，L=3则CEO至少要管理4名下属。因为假设CEO只管理3名下属，则整个公司最多容纳10名员工，如下图所示：

     1

  /  | 

 2   3   4

/ / /

5 6 7 8 9 10

输入

两个整数N和L。 (2 ≤ N, L ≤ 10¹⁸)

输出

一个整数代表答案。

样例输入

12 3

样例输出

4

题解

    管理的层次可以看做一棵树,假设根节点的下属有K个,那么这K个人最多各自管理(K-1)个,依次类推,显然总人数是各阶乘的和。在L层的限制下,上层的直接管理人员人数要大于下一层,能用L层就尽量用L层,而不是用 < L层,否则题目要求的直接管理人数会上升。如果用不到L层,比如人数很少,但是给了10000层,显然是用不到的,设直接下属人数为ans,也要往小了找ans。

    题目的层数可以达到10^18，所以寻找最小ans的话是不可以用暴力解法的。所以我们用二分法求解，对能满足总人数大于N且层数小于L层的K，二分K判断是不是能满足条件，并取满足条件的最小值。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
typedef long long LL;

int main() {
  long long n, L;
  while (scanf("%lld %lld", &n, &L) != -1) {
    if (L == 2) {
      printf("%lld
", n - 1);
    } else {
      long long low = 1, high = n - 1;
      while (low < high) {
        long long mid = (low + high) >> 1;
        long long sum = 0, num = mid + 1, ll = 1, x;
        while (num && ll <= L) {
          if (ll == 1) {
            x = 1;
          } else {
            if (n / x <= num) {
              sum = n;
              break;
            }
            x = x * num;
          }
          sum += x;
          if (n <= sum) {
            break;
          }
          ++ll;
          --num;
        }
        // to ensure when low = high - 1, the result will be true
        if (sum >= n) {
          high = mid;
        } else {
          low = mid + 1;
        }
      }
      printf("%lld
", low);
    }
  }
  return 0;
}

输入样例

Sample I/O:

in:20 3

out:5

because 20-1=19, and in the limit of 3,4+4*3<19<5+5*4, so answer is 5

in:1000000000000000000 2

out:1000000000