沉得好快，

没人做出来吗？（再没人做我只好自己解答了）

看不懂的贪心算法。好难，请给出详尽的解释以及你的理解，谢谢！

我对这道题的解答：（最好定义一个分数运算，保证准确度）

初看这个题目，我也有点摸不找头脑，方法是搜索（这是我想了一番后确定的）

我想最理想的情况是我搜索道的第一个解就是最优解（谁不希望这样）

先说搜索算法：以分2个为例：把以个分数分成两个，其中必有以个比原分数的1/2大，那么范围就有了，我只要搜索所有比原分数的1/2大的分数（很有限），然后判断另一个分数是否满足条件就可以了。搜索应该从满足条件最小的分数到最大的——这样可以保证第一次就搜索到最优解。

我已经把分两个的算法说了，由于要晚自习，没时间了，剩下的大家想想，我晚上放学再来看看。

再说分成N个的算法：

这N个数里面必然有一个比原数的1/N大，那我先找出所有满足条件的数。剩下的就变成了一个N-1的问题。

很明显是可以有第归函数解决的（定义一个分N份的函数，第归调用直到N=2）

当然这么搜索可能会重复，而且是否为最优还不得而知，解决得办法是让搜索有序化，这一次搜索到得数必须比上一

个小（这是我上一个题目的精华思想，在这里也起了大作用）这样得到的必定是最小得加数，要让这个数尽量大（最优

解得要求）就是前面得数尽量小，解决这个只要确定搜索方向就可以了——从小到大搜

举个例子：对于2/5大于它得一半的分数有：1/2，1/3，1/4我们把搜索方向确定为1/4到1/2，这样先搜索到得数总是比后搜索到得数小，也就是最后剩下得数会大。

把搜索函数写好后，先搜索N=2得情况，没有，再搜索N=3的情况，以次类推，

当然这样的搜索你可能会怀疑N太大时…… 其实就我目前的测试看来，还没出现过N>3的情况。

好了，有不懂的可以提出来。我又要去上学了。（如果需要我把代码也贴上来）

我有一个程序,但我看不懂（C++），请高手注释一下。在vc发了几天，根本没人回帖，还是c好！
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>
using namespace std;
const double zero=1e-20;
const double maxn=1e20;
int num;
bool bb;
double tempa[1000],tempb[1000],best[1000],v[1000];
int g_cd(int a,int b)
{
int ta,tb;
ta=a;tb=b;
if(ta<tb)swap(ta,tb);
if(!(ta%tb))return tb;
else return g_cd(tb,ta%tb);
}//求两个数的最大公约数
void solve(int x)
{
int i,next,prev;
if(x>num)
{
if(fabs(tempa[num])<zero)
{
bb=1;
if(v[num]<best[num])
for(i=1;i<=num;i++)
best[i]=v[i];
}
}else
{
prev=(int(tempb[x-1]/tempa[x-1])>int(v[x-1]+1))?int(tempb[x-1]/tempa[x-1]):int(v[x-1]+1);
next=int((num-x+1)*tempb[x-1]/tempa[x-1]+zero);
if(tempb[x-1]/tempa[x-1]+num-x+1>best[num])return;
for(i=prev;i<=next;i++)
{
v[x]=i;
tempa[x]=tempa[x-1]*i-tempb[x-1];
if(tempa[x]<0)continue;
tempb[x]=tempb[x-1]*i;
if(tempa[x]>-zero && int(tempa[x]*v[x]/tempb[x])<=num-x)
solve(x+1);
}
}
}
int main(int argc, char *argv[])
{
int i,j,n,temp,a,b;
cin>>n;
for(j=0;j<n;j++)
{
cin>>a>>b;
temp=g_cd(a,b);
a/=temp;b/=temp;
if(a==1)
cout<<b<<endl;
else
{
v[0]=b/a;num=1;
bb=0;best[1]=maxn;
while(1)
{
num++;
best[num]=maxn;
tempa[0]=a;tempb[0]=b;
solve(1);
if(bb)break;
}
for(i=1;i<num;i++)
cout<<setiosflags(ios::fixed)<<setprecision(0)<<best[i]<<' ';
cout<<best[num]<<endl;
}
}
//system("PAUSE");
return 0;
}

大家帮帮忙啊！谢谢了！

或者说说上面程序的思路

乌鸦丘比特 网上这个题的算法多的是！我就搞不明白为什么有很多人先后把这题一次又一次的发出来

就自己不能搜索一下？

天,楼上的也不看看这是什么时候的贴子

没看呀 25楼考古的料