首页 > 代码库 > 【水】弱化版魔术球问题
【水】弱化版魔术球问题
卖个萌
这是一个弱化版的魔术球问题,本来都不好意思丢上来。。。但是这几天都在看代码没有写东西,还是丢一下凑凑数吧。
不要问我正解哪里进,我也没找到,反正百度魔术球问题第一页都是错的。所有代码都跑不出结果。600这么low的数据没有一个所谓AC代码可以跑的过(似乎我代码加了输出方案也过不去。。)。所以后面我的数据600就是用没有加输出方案的我的弱弱的程序跑的。。。
我的代码加了输出方案丢在最后附数据的文章里面了。。错的,不过我会尽快改对的。。。。。
魔术球问题弱化版(ball.c/.cpp/.pas)
题目描述
假设有 n 根柱子,现要按下述规则在这 n 根柱子中依次放入编号为 1,2,3,…的球。
(1)每次只能在某根柱子的最上面放球。
(2)在同一根柱子中,任何 2 个相邻球的编号之和为完全平方数。
试设计一个算法,计算出在 n 根柱子上最多能放多少个球。例如,在 4 根柱子上最多可放 11 个球。
对于给定的 n,计算在 n 根柱子上最多能放多少个球。
输入描述
第 1 行有 1 个正整数 n,表示柱子数。
输出描述
一行表示可以放的最大球数
样例输入
4
样例输出。
11
题目限制(为什么说弱化版就在这里)
N<=60,时限为3s;比起原题还有弱化在不用打出方案,方案太坑了
思路 thinkings
这么小的范围60。。。我真心觉得可以打表。。为了尊重出题人吴桐,还是写个贪心吧。。
(QaQ:什么?你要我写网络流+最小路径覆盖?这只有60好吗。。n^5算法都可以过。。。)
贪心是这样滴:
第一个球球当然是放在第一个柱子里面了(柱子里面怎么能放球?(*^__^*) )
以后每一个球都从第一个柱子开始判断是否能放进去,如果可以的话就放啦,如果不行就新开一个啦。。不能再开就完啦。
代码 codes
#include<iostream>#include<cstdlib>#include<cstdio>#include<cmath> #include<cstring>using namespace std;int board[999999]={0};int wutong(int x){ double m=sqrt(x); if (int(m)==m) {return 1;} else {return 0;}}int main(){ int n; cin>>n; int all=1; int ans=2;board[1]=1; while (all<=n) { int flag=0; for (int t=1;t<=all;t++) if (wutong(board[t]+ans)==1) {flag=1;board[t]=ans;break;} if ((flag==0)&&(all<n)) {all++;board[all]=ans;flag=1;} if (flag==0) break; ans++; } cout<<ans-1<<endl; return 0;}
反思
1.看数据范围,小数据可以打表。。。
2.memset是需要时间的。。int a[99999999]={0}不需要时间。。。。
数据
不给数据似乎要打我。。
那我给个地址吧
http://www.cnblogs.com/seekdreamer/articles/3813891.html...
其中代码是错的。。。不过我一定会尽快改对的。。