第2题放书(noip2008mn)

第2题放书(noip2008mn)
作为一名图书管理员，每天结束时你要把书放回书架。书架和堆放书的地方可以认为在一个X轴上，堆书的地点坐标为0，书架的位置在正、负整数点上。你开始的位置就在0点，你一次最多可以拿N本书，问你最少要走多少路程才可以把书全部放回各自的书架上。

输入格式
第一行有两个整数K和N， 1<=K,N <=50，分别代表书本总数和你一次最多可拿的书本数。后面有K个整数(在-10000到10000之间)，分别表示每本书所要放回书架的位置。

输出格式
最少需要的路程。注：你最后可以停在任意的位置，不必返回到开始位置。

输入/输出例子1
输入：

7 2

-37 2 -6 -39 -29 11 -28

输出：

131

输入/输出例子2
输入：

8 3

-18 -9 -4 50 22 -26 40 -45

输出：

158

移动距离最少，需要每次将最远的同方向的N本书放到合适位置，当两侧书本数量都小于N时，跑两趟分别把两侧的书放到合适位置。因为不需要回到原来的地方，再减去最远的书的距离。
c++代码：


#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

template <typename T>
T max(T& a, T& b) {
    return a < b ? b : a;
}

int main() {
    int k, n, i, j, s = 0;
    cin >> k >> n;
    vector<int> v(k);
    for (i = 0; i < k; i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    for (i = 0; v[i] <= 0; i++);
    for (j = 0; j < i; j++) {
        if (j % n == 0) {
            s -= v[j] * 2;
        }
    }
    for (j = v.size(); j > i; j--) {
        if ((v.size() - j) % n == 0) {
            s += v[j - 1] * 2;
        }
    }
    s -= max(-v.front(), v.back());
    cout << s;
    return 0;
}

执行结果：

这是一道贪心算法问题。

首先，我们可以将所有书按照书架位置从小到大排序，然后可以每次从当前位置最近的书架开始拿书，直到拿满N本书为止。这样做的好处是我们可以保证每次移动的距离都是最小的。

代码如下：

k, n = map(int, input().split())
books = list(map(int, input().split()))
books.sort()

i = 0
ans = 0
while i < k:
    j = min(i + n, k) - 1
    ans += abs(books[j] - books[i])
    i = j + 1

print(ans)

时间复杂度为 O(n log n)，空间复杂度为 O(n)。

第2题 放书(noip2008mn)

第2题放书(noip2008mn)