我觉得应该分配给最大最小值
然后，最大最小值将内敛
重新分配给新的最大最小值
依次循环搞定
比值的分子分母一次调整，将涉及到比值本身跟相邻两个比值的调整
所以，并不是很容易能得到优化的
无心人 发表于 2013-8-24 08:23
我觉得应该分配给最大最小值
然后，最大最小值将内敛
我觉得根据等比公式计算出q，取圆整之后， q 的最大值和最小值 已经是 刚性的了，把配额 给他们两个的话，不仅达不到财富均匀的目的，反而会牵一发而动全身，引起骚乱。
应该分配给那种 肉大身沉，体量庞大的项，;P
另外，分给最后两项，不会影响前面的既得利益者。
当初为了发现规律，
我先用 Mathematica 解出浮点的公比，
然后打开 Excel，进行余下的半手工操作。
先人为的在数列之前加一项“1”，
计算出相邻数之比（后面的除以前面的），
找出最大者，将其对应的数-1，加在最小者对应的数上。
由于比例是除法关系，敏感度与分母的大小相关，
所以该微调若作用于前几项，甚至会让q_min、q_max发生变化，
而微调作用于较大的项上，则对评价值影响不那么敏感。
此即楼上 wayne 所总结的那样。
注：上述微调也许需要进行多次。
是否能证明或者证否这个：
根据等比公式计算出理想情况的浮点数q，各项取圆整之后，得到的圆整数列的 q 的最大值和最小值 已经是 刚性的了，即最优
当最优确定之后，多余的那部分财产，似乎只能分给最后一项，或者最后两项
好吧，我是倾向于逐渐调整的
你们是倾向于定向爆破
wayne 发表于 2013-8-24 08:39
是否能证明或者证否这个：
应该不是最优
当最优确定之后，多余的那部分财产，似乎只能分给最后一项，或者最后两项
由于圆整（可以理解为四舍五入）带来的误差，会对相邻项之比带来波动，
所以即便完成了多余财产（可正可负）的分配，往往仍需进行微调。
按照我的思路，做个穷举程序，
按照你们的思路，做个调整程序，
看两者得到的结果一致么
假设【前提$1$】成立，那么：
解决该问题的算法的时间复杂度的理论下界是$\Omega(n)$，
原因是将结果输出来就需要$\Omega(n)$的时间了。
但目前我只找到了时间复杂度为$O(n\log(s))$的算法，
该算法是确定的算法，输出结果一定是最优解，而且不需要使用浮点运算。
是否存在时间复杂度为$O(n)$的算法，我现在还不知道。
【前提$1$】：
任何两个$0$到$s$的整数进行一次代数运算或逻辑运算的时间复杂度是$O(1)$。
引入该前提是为了避免分析大数运算的时间复杂度。
#####
该算法的核心是二分法。
该算法一共有$2$个步骤。
步骤一：二分法确定首项
读入$n$和$s$，用二分法求$a_0$，使得：
$a_0+a_0^2+a_0^3+...+a_0^n\leq s$
$(a_0+1)+(a_0+1)^2+(a_0+1)^3+...+(a_0+1)^n>s$
步骤二：二分法确定公比
$1$、如果$a_0+a_0^2+a_0^3+...+a_0^n=s$，那么输出$a_0,a_0^2,a_0^3,...,a_0^n$，结束；否则继续下面的步骤。
$2a$、取公比$q$，满足$a_0<q<a_0+1$，令$a_1=\lfloor a_0*q\rfloor$、$a_2=\lfloor a_1*q\rfloor$、……
$3a$、如果$a_0+a_1+a_2+...+a_{n-1}<s$，则加大公比，否则减小公比。
$4a$、重复$2a$、$3a$，直到试遍$(a_0,a_0+1)$中所有可能的公比为止。
$2b$、取公比$q$，满足$a_0<q<a_0+1$，令$a_1=\lceil (a_0+1)*q\rceil$、$a_2=\lceil a_1*q\rceil$、……
$3b$、如果$a_0+a_1+a_2+...+a_{n-1}>s$，则减小公比，否则加大公比。
$4b$、重复$2b$、$3b$，直到试遍$(a_0,a_0+1)$中所有可能的公比为止。
$5$、假设$4a$试出来的公比是$q_a$，$4b$试出来的公比是$q_b$，比较$(q_a-a_0)$和$(a_0+1-q_b)$的大小，输出较小者及相应的数列。
#####
步骤一的时间复杂度是$O(n\log(s))$。
对于步骤二，要试的公比肯定都是分子和分母均不超过$s$的分数，这样的分数不超过$s^2$个。
因此步骤二的时间复杂度是$O(n\log(s^2))=O(n\log(s))$。
综上所述，该算法的时间复杂度是$O(n\log(s))$，且不需要浮点运算。