poj 3150 && poj 2976

题目：http://poj.org/problem?id=3150

题意：给出 n 个数构成一个环，给出 m d k，每一个数从它的两边（连续的）各找 d 个数和这个数相加 再取余m后更新这个数，问 k 次操作后，输出新的n 个数的顺序。

不知道怎么优化，看了别人的解析   http://hi.baidu.com/moon_1st/item/0381d80a85fd258a3d42e2f0，循环矩阵经过 k 次幂后仍然是循环矩阵，而且有 a[i][j] = a[i - 1][j - 1]成立，这样转移矩阵的下一列就可以由这一列转换过去，降低复杂度

题目：http://poj.org/problem?id=2976

0/1分数规划，按照二分的方法 从 0 到 1 查找， 对于每一对数(ai,bi)，计算 ai-mid*bi 的大小。然后进行排序，选择最大的n-k个数字，求出他们的和，如果总和大于0，说明结果偏小，所以left = mid 否则 right = mid

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#define esp 0.000001
#define N 1010

using namespace std;

int a[N],b[N];
double t[N];
int main()
{
    int i;
    int n,k;
    while(scanf("%d%d",&n,&k) && (n + k))
    {
        for(i = 0; i < n; i++)
        scanf("%d",&a[i]);
        for(i = 0; i < n; i++)
        scanf("%d",&b[i]);
        double left,right,mid;
        left = 0;
        right = 1;
        while(fabs(left - right) >= esp)
        {
            mid = (left + right) / 2;
            for(i = 0; i < n; i++)
            t[i] = a[i] - mid * b[i];
            sort(t,t + n);
            double sum = 0;
            for(i = k; i < n; i++)
            sum += t[i];
            if(sum > 0) left = mid;
            else right = mid;
        }
        //mid *= 100;
        left *= 100;
        printf("%.0lf\n",left);
    }
    return 0;
}