石子游戏(后缀和)

有 n 堆石子，石子数量分别为 a1,a2,…,an。

现在，需要你通过取石子操作，使得所有堆石子的数量都相同。

一轮取石子操作的具体流程为：

1. 设定一个石子数量上限 h
2. 检查每堆石子，对于石子数量大于 h的石子堆，取出多余石子，使其石子数量等于 h

• 要求，在一轮取石子操作中取走的石子数量不得超过 k
• 请计算并输出为了使得所有堆石子的数量都相同，最少需要进行多少轮取石子操作。

• 输入格式

  第一行包含两个整数 n,k。

  第二行包含 n个整数 a1,a2,…,an。

  输出格式

  一个整数，表示所需的最少取石子操作轮次。

  数据范围

  前六个测试点满足， 1≤n≤k≤10。

  所有测试点满足，1≤n≤2×10^5，n≤k≤10^9，1≤ai≤2×10^5。

  输入样例1：

  
      
  
       
  
        
  
         
  
        
        
  
         
  
          5 5
         
        
       
  
        
  
         
  
        
        
  
         
  
          3 1 2 2 4
         
        
      
     
  

  输出样例1：

  2
  
     
  

  输入样例2：

  
      
  
       
  
        
  
         
  
        
        
  
         
  
          4 5
         
        
       
  
        
  
         
  
        
        
  
         
  
          2 3 4 5
         
        
      
     
  

  输出样例2：

  2
  
     
  

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <cstring>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef long long LL;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int a[200005], n, m;
     
    
   

    

     

    
    

     

      LL c[200005];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main() {
     
    
   

    

     

    
    

     
    scanf("%d%d", &n, &m);
     
    
   

    

     

    
    

     
    int mins = 2e5;
     
    
   

    

     

    
    

     
    for (int i = 1; i <= n; ++i) {
     
    
   

    

     

    
    

     
        scanf("%d", a + i);
     
    
   

    

     

    
    

     

              ++c[a[i]];//桶装法 看个数
     
    
   

    

     

    
    

     
        if (a[i] < mins) mins = a[i];//最小值，进行轮数最少，那么就要把所有都变成堆堆中的最小即可
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    int res = 0;
     
    
   

    

     

    
    

     

          LL cur = 0;
     
    
   

    

     

    
    

     
    for (int i = 2e5; i > mins; --i) {
     
    
   

    

     

    
    

     

              c[i] += c[i + 1];//后缀和 表示由后往前一共有多少《堆》石子，模拟从高度h到高度h-1取石子，因为高度为h-1的石子包含了最高层为h-1的石子，以及比h更高的石子
     
    
   

    

     

    
    

     
        if ((cur += c[i]) > m) {//大于了一轮的数目，那么最后就要下一轮
     
    
   

    

     

    
    

     

                  ++res, cur = c[i];
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    printf("%d\n", res + !!cur);//！！ 把非0转化为1 把0转化成0
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

这个题巧妙地用到了后缀和，同时向我们展示了石子堆砌的魅力。

首先看每个高度有多少石子，其次看高度的最小值。

要把所有的石子变到这个高度。

那么，高度为h 就有c[h]个，

高度为h-1就有c[h-1]个，

以此类推。

最后如果手上还有石子，利用!!判断，直接加上即可。

文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_54227557/article/details/120589249