首页 > 代码库 > 【水】弱化版魔术球问题

【水】弱化版魔术球问题

卖个萌

这是一个弱化版的魔术球问题,本来都不好意思丢上来。。。但是这几天都在看代码没有写东西,还是丢一下凑凑数吧。

不要问我正解哪里进,我也没找到,反正百度魔术球问题第一页都是错的。所有代码都跑不出结果。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...

其中代码是错的。。。不过我一定会尽快改对的。。