zjn 的积木高塔

题目描述

zjn 有 n 块积木，每块积木的高度都相同，但是底面面积不同，第 i 块积木的底面面积为 wi

现在 zjn 用这些积木来搭一个 k 层高的高塔，每一层只用一块积木，而为了高塔的稳定，对于

相邻两层的积木来说，下层积木的底面面积必须是上层积木的两倍以上

现在 zjn 想知道，自己最多能搭几个 k 层的高塔？

输入格式

第一行两个正整数 n, k，分别表示积木的块数，以及高塔的层数。

第二行 n 个正整数 wi，分别表示每块积木的底面面积。

输出格式

输出一行一个整数，表示最多可搭建的高塔的个数。

数据范围对于 30% 的数据满足:n, k ≤ 7

对于 100% 的数据满足:2 ≤ n ≤ 2 ∗ 105, 2 ≤ k ≤ 30, k ≤ n, 1 ≤ wi ≤ 231

样例输入

9 3

6 1 11 4 8 7 2 18 3

样例输出

2

样例解释

其中一组方案，两个高塔分别是：{
1 2 4},{
3 7 18}

题解

很容易发现答案具有单调性，由此想到二分答案，此题主要难点在于check。

很多人第一反应为排序后，每栋楼贪心取最小的能放的积木。

但这个贪心是错的，对于

6 3

1 2 4 8 8 16

这组数据，这种贪心只能搭建一个高塔楼(1, 2, 4)，剩下的$(8,8,16)则无法搭第二个。

但事实上，可以(1, 4, 8)一组，(2,8,16)一组就能搭两个高塔。

因此考虑更换贪心策略。考虑二分高塔数的的情况下，一层一层贪心搭建，每次对于每个高塔

的这一层找到能放的最小积木。

标程

#include<bits/stdc++.h> #define int long long using namespace std; int n,k,l,r,ans,mid,a[],t[]; bool f(int m) { memset(t,0,sizeof(t)); int id = 0; for(int i = 1; i <= k; i++) { for(int j = 1; j <= m; j++) { id++; while(a[id] < t[j] * 2) { if(id > n) return 0; id++; } t[j] = a[id]; } } return 1; } signed main() { //freopen("block.in","r",stdin); //freopen("block.out","w",stdout); scanf("%lld%lld",&n,&k); r = n; for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); sort(a + 1,a + n + 1); while(l <= r) { mid = (l + r) / 2; if(f(mid) == 1) { l = mid + 1; ans = mid; } else r = mid - 1; } printf("%lld", ans); return 0; }