gym101194 china final Problem D. Ice Cream Tower(二分)-白红宇的个人博客

gym101194 china final Problem D. Ice Cream Tower(二分)

发布日期：2021-11-12 00:25:57 浏览次数：1 分类：技术文章

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

Problem D. Ice Cream Tower

Input file:Output file: Time limit:

Standard InputStandard Ouptut6 seconds

The 2016 ACM-ICPC Asia China-Final Contest

Mr. Panda likes ice cream very much especially the ice cream tower. An ice cream tower consistsof K ice cream balls stacking up as a tower. In order to make the tower stable, the lower ice creamball should be at least twice as large as the ball right above it. In other words, if the sizes of theice cream balls from top to bottom are A0, A1, A2, ···, AK−1, then A0 ×2 ≤ A1, A1 ×2 ≤ A2,etc.

One day Mr. Panda was walking along the street and found a shop selling ice cream balls. Thereare N ice cream balls on sell and the sizes are B0, B1, B2, ···, BN−1. Mr. Panda was wonderingthe maximal number of ice cream towers could be made by these balls.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each testcase starts with a line consisting of 2 integers, N the number of ice cream balls in shop and Kthe number of balls needed to form an ice cream tower. The next line consists of N integersrepresenting the size of ice cream balls in shop.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number(starting from 1) and y is the maximal number of ice cream towers could be made.

Limits

• 1≤T ≤100.

• 1 ≤ N ≤ 3 × 105.• 1 ≤ K ≤ 64.

• 1≤Bi ≤1018.

Sample input and output

Sample Input	Sample Output
3 42 1234 6311224463112234	Case #1: 2Case #2: 2Case #3: 1

题意：

给出n个冰淇淋球，做一个冰淇淋需要k个冰淇淋球，并且规定对于上下相邻的两个球，下面的球的质量大于等于其上面的那个球质量的两倍。

后面一行n个数，给出n个球的质量，问最多能做出多少个冰淇淋？

题解：

这题可以二分，假设能做x个冰淇淋，那么先安排最上面那个球，贪心的思想，肯定取最小的x个，然后后面的类似取，线性扫一遍n，判断能否取x个。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define rep(i,a,n) for (int i=a;i
          
           =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
           
             VI;typedef long long ll;typedef pair
            
              PII;const int maxn=3e5+100;ll a[maxn],b[maxn];int n,k;bool check(int x){ if(!x) return true; int j=x+1; rep(i,1,x+1) { b[i]=a[i]; } int i; for(i=x+1;i<=n;) { while(a[i]
             
              <=n) i++; if(i>n) break; b[j++]=a[i]; if((j-1)/x>=k) return true; i++; } if((j-1)/x>=k) return true; else return false;}int main(){ int cas; scanf("%d",&cas); rep(kk,1,cas+1) { scanf("%d%d",&n,&k); rep(i,1,n+1) scanf("%lld",&a[i]); if(n

转载地址：https://blog.csdn.net/fouzhe/article/details/56667158 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：gym 101170 Problem H Hamiltonian Hypercube(找规律?)

下一篇：gym101194 china final Problem E. Bet(数学,高精度)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章