Mcdull28
2018-03-23 03:22
采纳率: 100%
浏览 978
已采纳

一个C语言算法题目,帮忙给个思路

【问题描述】
现有n堆球,其中n是偶数,第i堆中有 ai 个球。现需要将其中 n / 2 堆中的球数全变成完
全平方数,另外的 n / 2 全不为完全平方数。你每一次操作可以选择任意一堆增加或拿走(前
提不为 0)一个球。试问最少需要多少次操作可以满足要求。
【输入】
第一行输入n (2 ≤n ≤ 200 000)为球的 堆数。
第二行输入n个的非负整数 a1, a2, ..., an (0≤ ai ≤ 109) 每堆的球数。
【输出】
输出最少的操作步数。
【输入样例】
4
12 14 30 4
【输出样例】
2
【输入样例】
6
0 0 0 0 0 0
【输出样例】
6

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • 辛潇 2018-03-23 03:38
    已采纳

    求出每个数凑成平方数的最小步数之后从小到大排序,求前面一半的和就可以了

    点赞 打赏 评论
  • zjq_01 2018-03-25 11:57

    首先找到每个球的最近的完全平方数~
    然后作差值看看是多少,翻译成差值后取其绝对值进行快速排序既可化简结果~
    时间复杂度预计为o(n*log(n));

    点赞 打赏 评论
  • 黑柯与梦 2021-07-15 19:55

    题目叫什么

    点赞 打赏 评论

相关推荐 更多相似问题