本校同学想要代码的邮件我
sgu的数据太强了，真是太折磨人了
sgu115:calendar
sgu的水题
sgu114:找中位点
算法导论Excercise 9.3-9的题目
看了答案之后我的理解性简单证明：
1.sgu的题目等价于有n个点，每个点有一个人，p个人的话，可以看作是p个坐标相同的点。
2.考虑n的节点个数
设此时的左半边的费用和设为a ,右半边的费用和设为b
如果n是偶数
设最优解坐标为x1,x2
*假设最优解在n / 2 和 n / 2 + 1两个点之间
Cost = a + b;
如果移动最优解的坐标，很容易可以证明
只要坐标还在两个中位点之间，那么解的值就不变。假设在两个中位点之间左移d个单位
Cost = a - (n/2) * d + b + (n/2) * d
= a + b;
右移同理
*假设向左移出了中位点的距离
Cost = a - (n/2-1) * d + b + (n/2-1) * d + x2 - x1 + d
= a + b + d;
如果移动超过这两个点，那么解的值都将变大
如果n是奇数
*设最优解坐标为x,最优值一定在中位点上。
此时Cost = a + b;
*假设最优解左移d个单位
此时Cost = a - (n/2)*d + b + (n/2)*d + d
= a + b + x - d
向右移同理
所以中位点是最优值
114此题就是多了个计数和排序
sgu113:素数
可以发现，只要求sqrt(1000000000) 个素数即可,也就是判断tmp = m / primes[i]
判断tmp是否是素数即可
trick是，tmp可能大于sqrt(1000000000)!!
sgu112:大数幂
sgu111:大数求平方根
方法很多，大多数人都是模拟手算开方，我看了半天没看明白，于是弄了哥迭代法 + java 水过
稍微有一点猥琐...
c++版的求平方根方法
double eps = 1e-8;
int main()
{
int x,i,j,k;
while(scanf("%d",&x) == 1) {
double r = x; //尽量靠近sqrt(x)，这里是为了一个通解
double p = 1;
while(p + eps < r) {
r = (r + p) / 2;
p = x / r;
}
printf("%f\n",r);
}
return 0;
}
原版的算法，我改了改
1. Start with an arbitrary positive start value r (the closer to the square root of x, the better).
2. Replace r by the average between r and x/r, that is: (r + x/r) / 2 ,
(It is sufficient to take an approximate value of the average in order to ensure convergence.)
3. Repeat step 2 until r and x/r are as close as desired.