Advertisement

中位数题解 C++ 详细版

阅读量:

拙笔如下

所探讨的问题如下

复制代码
    题目描述:
    给你n个整数ai和一个整数s,题目数据保证n是奇数。
    1次操作可以使n个数中的任意一个数增加1或者减少1。
    你现在的任务是计算出使这n个整数的中位数变为s的最小操作数是多少?
    
    
      
      
      
      
    
复制代码
    输入格式:
    输入一共有两行。
    第一行有两个整数n和s,分别表示整数的个数和题目描述的s的值
    第二行包含n个用空格分开的整数,a1,a2,a3,...,an。
    
    
      
      
      
      
    
复制代码
    输出格式:
    输出只有一个整数,表示最小操作数。
    
    
      
      
    

这道题目在我看来存在陷阱

中位数并非初始状态,完成一次操作后还需继续处理,直至满足条件。否则这将只是一道简单的题目

我最初的思路是:先进行一次操作,接着进行排序,再继续处理……

结果却导致了:Time Limit Exceeded

显然,我是在冒险(不冒险就不会失败)

随后我寻求了 CJG 的帮助,并自行思考了一番,最终解决了这道题

具体步骤如下:

全部评论 (0)

还没有任何评论哟~