回 帖 发 新 帖 刷新版面

主题:还是题目:数组,此乃本人弱项


[fly]再次衷心感谢各位[/fly]
还有2题
1.问题描述:
火车从始发站(称为第一站)开出,在始发站上车的人数为 a ,然后到达第2站, 在第2站有人上、下车,但上、下车的人数相同,因此在第2站开出时(即在到达第3站之前)车上的人数保持为 a 人。从第3站起(包括第3站)上、 下车的人数有一定的规律:上车的人数都是前两站上车人数之和,而下车人数等于上一站上车人数,一直到终点站的前一站(第 n-1 站), 都满足此规律。现给出的条件是:共有 n 个车站,始发站上车的人数为 a ,最后一站下车的人数是 m(全部下车)。试问从 x 站开出时车上的人数是多少? 
输入共有四个整数,数与数之间用空格分隔,分别为a,n,m 和 x。
输出只有一个整数,从 x 站开出时车上的人数。
输入输出样例:
INPUT:
23  15  6351  6
OUTPUT:
144
2.问题描述:
有N个盒子(N≤1000),编号分别为1,2,…,N。每个盒子可装入任何数量的球。同时有K个小球(N≤K≤10000)。小球装入盒子的规则:
⑴第1个盒子不空。
⑵装入必须按递增顺序进行。例如当K=8,N=6时,装入方法有1、2、5或1、3、4
⑶在满足条件⑴⑵下,有球的盒子尽可能多。
⑷装完后,相邻盒子中球数差的绝对值之和最小(未装盒子不计)。
例如上例中
装入法:   1   2   5          1   3   4
差的绝对值之和:   2 – 1 + 5 – 2 = 4           3 –1 + 4 – 3 = 3
问题求解:
由键盘输入N(盒子数)和K(球数)。打印输出符合要求的装入方法。
输入输出示例:
INPUT:
N= 6
K = 8
OUTPUT:
1  3  4
[em18][em18][em1]

回复列表 (共3个回复)

沙发

只提供一下第二题的思路吧。。。
第二题:当n*(n+1)>=2*k的话就说明盒子太多,只要输出1  2  3.。。。。j    k-j*(j+1)/2
其中j表示所有满足j*(j+1)<=2k的最大正整数。
当n*(n+1)<2*k的话就说明盒子太少,要动归:
f[i,j]=min{f[i-1,k]+j-k},1<=k<j,j>=i,1<=j<=总小球数
其中f[i,j]表示当前到i盒子时放j个小球差值最小的那个最小值,k枚举的是前一个位置所放的球数。
当然,如果要输出放法的话就要另开一个g数组记录f[i,j]是由哪个继承得到的(记为g[i,j])最后逆序输出即可。。。
当然,如果您要求1s内出解的话我这个当n*(n+1)<2*k时显然不行,但是先抛砖引玉吧。。。

偶的FP坏了,无法写程序,请见谅。。。

以上。。。。

板凳

第一题是模拟,
第二题可以暴公式:
(x+(x+n))*(n+1)/2-θ=s (其中x为起始数,θ是跳过的,满足x≤θ≤x+n)
x[sup]2[/sup]+nx-(2s+2θ)/(n+1)=0

Δ=n[sup]2[/sup]+8(s+θ)/(n+1)
=sqr(向上取整(sqrt(n[sup]2[/sup]+8s/(n+1))))

x=(Δ-n)/2
θ=(Δ[sup]2[/sup]-n[sup]2[/sup]-8s/(n+1))*(n+1)/8

输出x~θ-1,θ+1~x+n+1

3 楼

第一题是模拟,
第二题可以暴公式:
(x+(x+n))*(n+1)/2-θ=s (其中x为起始数,θ是跳过的,满足x≤θ≤x+n)
x[sup]2[/sup]+nx-(2s+2θ)/(n+1)=0

Δ=n[sup]2[/sup]+8(s+θ)/(n+1)
=sqr(round(sqrt(n[sup]2[/sup]+8s/(n+1))))

x=(Δ-n)/2
θ=(Δ[sup]2[/sup]-n[sup]2[/sup]-8s/(n+1))*(n+1)/8

输出x~θ-1,θ+1~x+n+1

可能推导有错,没检查

我来回复

您尚未登录,请登录后再回复。点此登录或注册