[코드포스 Practice7] D. Array Splitting

You are given a sorted array a1,a2,…,ana1,a2,…,an (for each index i>1i>1 condition ai≥ai−1ai≥ai−1 holds) and an integer kk.

You are asked to divide this array into kk non-empty consecutive subarrays. Every element in the array should be included in exactly one subarray.

Let max(i)max(i) be equal to the maximum in the ii-th subarray, and min(i)min(i) be equal to the minimum in the ii-th subarray. The cost of division is equal to ∑i=1k(max(i)−min(i))∑i=1k(max(i)−min(i)). For example, if a=[2,4,5,5,8,11,19]a=[2,4,5,5,8,11,19] and we divide it into 33 subarrays in the following way: [2,4],[5,5],[8,11,19][2,4],[5,5],[8,11,19], then the cost of division is equal to (4−2)+(5−5)+(19−8)=13(4−2)+(5−5)+(19−8)=13.

Calculate the minimum cost you can obtain by dividing the array aa into kk non-empty consecutive subarrays.

 

Input

The first line contains two integers nn and kk (1≤k≤n≤3⋅1051≤k≤n≤3⋅105).

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109, ai≥ai−1ai≥ai−1).

Output

Print the minimum cost you can obtain by dividing the array aa into kk nonempty consecutive subarrays.

---

 

 

이거 전에 막 공유기 문제도 생각나고 뭔가 연속되어 있고 양 옆의 값 활용하는 것 같아서 투포인터도 생각나고.. 그래서 이런거 관련 문제인가??? 싶었다. (아직 아는 게 적어 이 두개밖에 대입 못해봄ㅜ.ㅜ) 아 근데 아니었다ㅎ 

 

 

두번째 트라이

 

먼저 저걸 한 덩어리로 생각해서 v[n-1]과 v[0]의 차를 구했다. 이제 두 덩어리로 나누는데 어떻게 하면 합을 가장 작게 할 수 있을까 생각해보니 한칸 간격의 차가 가장 큰 걸 기준으로 나누면 되겠다 싶었다. 다음 세덩어리로 나눌 때도 차가 가장 큰걸로.. 이렇게 생각해보니 그냥 차를 계산한 뒤 정렬해서 가장 큰 것부터 빼면 될 것 같았음. 

 

해결!!

 

include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    
    vector<i64> v(n);
    vector<i64> sub(n-1);
    
    for(int i = 0; i < n; i++){
        scanf("%ld", &v[i]);
    }
    
    for(int i = 0; i < n-1; i++){
        sub[i] = v[i+1] - v[i];
    }
    
    i64 sum = v[n-1] - v[0];
    sort(sub.begin(), sub.end(), greater<i64>());
    
    for(int i = 0; i < k-1; i++){
        sum -= sub[i];
    }
    
    printf("%ld", sum);
    
    return 0;
}

코드는 이렇게 짰다.

 

문제 봤을 때 인접한 걸로 어떻게 하면 될꺼라는 생각은 들었는데 저걸 한 덩어리 -> 작은 덩어리로 나눠가며 푸는거에서 막혔다. 알아둬야지 흐흐