Codility - Lesson 14: TieRopes (Tie Ropes)

Lesson 14: TieRopes (Tie Ropes)

There are N ropes numbered from 0 to N − 1, whose lengths are given in a zero-indexed array A, lying on the floor in a line. For each I (0 ≤ I < N), the length of rope I on the line is A[I].

We say that two ropes I and I + 1 are adjacent. Two adjacent ropes can be tied together with a knot, and the length of the tied rope is the sum of lengths of both ropes. The resulting new rope can then be tied again.

For a given integer K, the goal is to tie the ropes in such a way that the number of ropes whose length is greater than or equal to K is maximal.

For example, consider K = 4 and array A such that:

    A[0] = 1
    A[1] = 2
    A[2] = 3
    A[3] = 4
    A[4] = 1
    A[5] = 1
    A[6] = 3

The ropes are shown in the figure below.

We can tie:

• rope 1 with rope 2 to produce a rope of length A[1] + A[2] = 5;
• rope 4 with rope 5 with rope 6 to produce a rope of length A[4] + A[5] + A[6] = 5.

After that, there will be three ropes whose lengths are greater than or equal to K = 4. It is not possible to produce four such ropes.

Write a function:

int solution(int K, int A[], int N);

that, given an integer K and a non-empty zero-indexed array A of N integers, returns the maximum number of ropes of length greater than or equal to K that can be created.

Assume that:

• N is an integer within the range [1..100,000];
• K is an integer within the range [1..1,000,000,000];
• each element of array A is an integer within the range [1..1,000,000,000].

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

http://blog.csdn.net/caopengcs/article/details/41841625

给定n段绳子——一个正整数数组，和一个正整数K，每次只能连接相邻的两根绳子，连接好了绳子长度为之前的绳子长度和，并且位置不变，问这么连接下去，最多能形成多少根长度至少为K的绳子？

数据范围： N[1..10^5], 数组元素和K的范围[1..10^9]。

要求复杂度： 时间O(N), 空间O(1)。

分析： 假设最终扔掉一根绳子，那么为什么不把这根绳子连接到它相邻的绳子上呢？ 所以不会扔绳子的…… 于是就线性扫一下 总和 >= K就是一条。。。

1. int solution(int K, vector<int> &A) {  
2.     int r = 0;  
3.     for (int i = 0; i < A.size();) {  
4.         int length = 0;  
5.         for (; (i < A.size()) && (length < K); length += A[i++])  
6.         ;  
7.         if (length >= K) {  
8.             ++r;  
9.         }  
10.     }  
11.     return r;  
12.       
13. }  

https://github.com/acprimer/Codility/blob/master/src/Lesson14/TieRopes.java
    public int solution(int K, int[] A) {
        int ans = 0, sum = 0;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            if (sum >= K) {
                ans++;
                sum = 0;
            }
        }
        return ans;
    }
Please read full article from Lesson 14: TieRopes (Tie Ropes)