acm 复习（下）

acm

1. 完成ddl

题意概述：有n件工作，每件工作有一个deadline，di。程序员小明预计完成对应工作i的时间为 bi。但是如果支付给小明x元，那么他完成这件工作的时间就变为bi - ai * x。现在BOSS想花费最少的钱，便可以保证所有工作都在其deadline之前完成。如果您是公司的CFO，求出最低花费。

解：比较一下所有工作完成时间的总和和最后一个ddl比较。可以算出来是否需要购买时间。如果需要，然后来用最少的钱来买这些时间。但是需要注意的是每个价格时间最多可以买多少呢？那就是 ai = bi/x >= 0。如果最廉洁的时间买完了，那就买次廉价的时间，知道可以满足ddl前完成所有的工作。

2. 计算哈夫曼树权值

题目概述：哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。

解：

1）cin >> n, n 是结点个数
2) cin >> arr[i], for i in (0,n)
3) sort(arr,arr+n,func), 降序排列
4) 1, 2, 4, 8...,2*n分别为第一二三...n 层的节点个数
5) 取出arr第一个元素*1, 取出第二第三个元素*2, ...
// 参考代码
double huffman() {
    int n;
    int pre = 0; 
    int post = 1;
    int flag = 1;
    double arr[100];
    double ans = 0;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    sort(arr, arr + n, func);
    if (n <= 2)
        return accumulate(arr, arr + n,0);
    else {
        while (1) {
            for (int i = pre; i < pre + post; ++i) {
                if (i >= n)
                    return ans;
                ans += flag * arr[i];
            }
            pre = pre + post;
            post *= 2;
            flag += 1;
        }
    }
}
bool func(double x, double y){
    return x >= y;
}

3. Whose sum is 0

Description:
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) ∈ A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n .
思路：二分加法暴力匹配
把左边两组数和右边两组数的n*n种情况的和算出来，最后满足 a+b = -(c+d)就说明满足四个数相加等于零。

4. 8G Island

Description:
The input contains multiply test cases(<= 10). Each test case contains three parts:
1 Three integers N, M(1 <= N,M <= 100000) and K(1 <= K <= N*M) in a line, as mentioned above.
2 N integers in a line, the charm value of each boy.
3 M integers in a line, the charm value of each girl.
All the charm values are integers between 1 and 100000(inclusive).
Process to the end-of-file.
解答：
把所有可能的“8g island”求出来，然后进行排序。接着用二分搜索所求“8g island”在这个序列的位置。时间复杂度N*M。