Broken Cabins Problem Statement: There is an Office consisting of m cabins enumerated from 1 to m. Each cabin is 1 meter long. Sadly, some cabins are broken and need to be repaired. You have an infinitely long repair tape. You want to cut some pieces from the tape and use them to cover all of the broken cabins. To be precise, a piece of tape of integer length t placed at some positions will cover segments 5,5+1-sit-1. You are allowed to cover non-broken cabins, it is also possible that some pieces of tape will overlap. Time is money, so you want to cut at most k continuous pieces of tape to cover all the broken cabins. What is the minimum total length of these pieces? Input Format
Broken Cabins
Problem Statement:
There is an Office consisting of m cabins enumerated from 1 to m. Each cabin is 1 meter long. Sadly, some cabins are broken and need to be repaired.
You have an infinitely long repair tape. You want to cut some pieces from the tape and use them to cover all of the broken cabins. To be precise, a piece of tape of integer length t placed at some positions will cover segments 5,5+1-sit-1.
You are allowed to cover non-broken cabins, it is also possible that some pieces of tape will overlap.
Time is money, so you want to cut at most k continuous
pieces of tape to cover all the broken cabins. What is the
minimum total length of these pieces?
Input Format
The first line contains three integers n,m and k(1sns10°, namsloº, Isksn) - the number of broken cabins, the length of the stick and the maximum number of pieces you can use
The second line contains n integers bl,b2,bn (Isbism) - the positions of the broken cabins. These integers are given in increasing order, that is, bl
Output Format:
Print the minimum total length of the pieces
Input:
Input:
4 100 2
20 30 75 80
Output
17
Step by step
Solved in 2 steps with 1 images