首页 > 代码库 > 魔术球问题弱化版 题解
魔术球问题弱化版 题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
我也不知道这个问题是哪里来的，所以没有题目链接...但是文末会给出几组数据。
题目描述
假设有 n 根柱子，现要按下述规则在这 n 根柱子中依次放入编号为 1，2，3，…的球。
（1）每次只能在某根柱子的最上面放球。
（2）在同一根柱子中，任何 2 个相邻球的编号之和为完全平方数。
试设计一个算法，计算出在 n 根柱子上最多能放多少个球。
例如，在 4 根柱子上最多可放 11 个球。
对于给定的 n，计算在 n 根柱子上最多能放多少个球。
输入描述
第 1 行有 1 个正整数 n，表示柱子数。
输出描述
一行表示可以放的最大球数。
样例输入：4
样例输出：11
题目限制（为什么说弱化版就在这里）
N<=60
分析：
这题已经水得不要不要的......
贪心直接做就可以。每次都把新的数从第一个柱子开始放，合适的话就放下，不合适换下一个柱子。
上面的贪心证明起来难度很大，但是“看起来好像很对的样子”。
AC代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 inline void read(int &x) 7 { 8 char ch = getchar();char c;x = 0; 9 while(ch < ‘0‘ || ch > ‘9‘) c = ch,ch = getchar();10 while(ch >= ‘0‘ && ch <= ‘9‘) x = x*10+ch-‘0‘,ch = getchar();11 if(c == ‘-‘) x = -x;12 }13 const int MAXN = 300 ;14 int post[MAXN];//记录某柱子最顶端的数字 15 int main()16 {17 int n,x,ans = 0;18 read(n);19 int i = 1;20 for(;;i ++)21 {22 for(int j = 1;j <= n;j ++)23 {24 x = sqrt(i + post[j]);25 if(x*x == i+post[j] || post[j] == 0)26 {27 ans ++;28 post[j] = i;29 break;30 }31 if(j == n)32 {33 printf("%d",ans);34 return 0;35 }36 }37 }38 }
测试数据：
输入#1：10 输出#1：59
输入#2：17 输出#2：161
输入#3：50 输出#3：1299
输入#4：60 输出#4：1859
输入#5：1 输出#5：1
魔术球问题弱化版 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。