Educational Codeforces Round 69 (Rated for Div. 2) C - Array Splitting

素颜马尾好姑娘i 2021-11-22 11:50 164阅读 0赞

[Educational Codeforces Round 69 (Rated for Div. 2)][Educational Codeforces Round 69 _Rated for Div. 2]

[C - Array Splitting][]

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

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

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

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

**Input**

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

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

**Output**

Print the minimum cost you can obtain by dividing the array a into k nonempty consecutive subarrays.

**Examples**

**input**

6 3

4 8 15 16 23 42

**output**

**input**

4 4

1 3 3 7

**output**

**input**

8 1

1 1 2 3 5 8 13 21

**output**

**Note**

In the first test we can divide array a in the following way: \[4,8,15,16\],\[23\],\[42\].

**题意：题意大概是 定义一个子数组代价为 数组里的最大值减去最小值，然后 给我们一个有序数组和一个k值，**

**问 把这个数组分成k个子数组的最小的总价值。**

**思路：先拿样例数组 【4 8 15 16 23 42】举例，**

**首先当k等于1时，当前代价就是原数组的代价为 最大值减最小值 （42 - 4） = 38;**

**当k等于2时，当前代价可以为 （8 - 4）+（42 - 15）= 31； 或者 （15 - 4）+（42 - 16）= 37 ...**

**求 最小代价 列举之后 发现应该是 （23 - 4）+（42 - 42）= 19。**

**这时候你可能发现了，当数组分成子数组时，有一段相邻元素的差值将不被算入代价，**

**例如上面的例子最小值 19 就是 相邻元素 （23，42）的差值 19 未被算入 ，然后就是 38-19=19。**

**然后拓展，k变大时，只需要去除k-1个相邻元素差值大的，就可以计算出最小代价，由此得解。。。**

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cmath>
     4 #include<cstring>
     5 #include<algorithm>
     6 #include<map>
     7 #include<set>
     8 #include<vector>
     9 #include<queue>
    10 using namespace std; 11 #define ll long long 
    12 const int mod=1e9+7; 13 const int inf=1e9+7; 14  
    15 const int maxn=3e5+5; 16 int num[maxn]; 17  
    18 int main() 19 { 20     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 21     int n,k; 22     
    23     while(cin>>n>>k) 24 { 25         vector<int>v; 26         ll int ans=0; 27         int x; 28         for(int i=0;i<n;i++) 29 { 30             cin>>num[i]; 31             
    32             if(i>0) 33 { 34                 x=num[i]-num[i-1]; 35                 ans+=x;//预处理 
    36 v.push_back(x); 37 } 38 } 39         
    40         sort(v.begin(),v.end(),greater<int>());//由大到小排序 
    41         k--;//去除k-1个相邻差值 
    42         
    43         for(int i=0;i<k;i++) 44             ans-=v[i]; 45         
    46         cout<<ans<<endl; 47 } 48     
    49     return 0; 50 }

转载于:https://www.cnblogs.com/xwl3109377858/p/11240237.html

[Educational Codeforces Round 69 _Rated for Div. 2]: https://codeforc.es/contest/1197
[C - Array Splitting]: https://codeforc.es/contest/1197/problem/C