codeforces 1197 C Array Splitting 贪心

2019/7/24 17:24:14 人评论 次浏览 分类:学习教程

http://codeforces.com/problemset/problem/1197/C

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

12

Input

4 4
1 3 3 7

Output

0

Input

8 1
1 1 2 3 5 8 13 21

Output

20

Note

In the first test we can divide array a

in the following way: [4,8,15,16],[23],[42].

思路:令数组d满足d[i]=a[i+1]-a[i],设sum[i]为数组d的前缀和,那么原序列[i,j]的花费就等于a[j]-a[i]=d[i]+d[i+1]+……+d[j],也即sum[j]-sum[i-1],在原序列[i,j]中以a[k]分段(a[i]及其左侧为一段 a[i]右侧为一段)则花费变为:a[k]-a[i]+a[j]-a[k+1],也即sum[j]-sum[i-1]-d[k],然后就想到贪心的做法了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;

int n,k;
int a[300005];
int d[300005];
ll ans=0;

int main()
{
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n-1;i++)
        d[i]=a[i+1]-a[i];
    sort(d,d+n-1);
    ans=a[n-1]-a[0];
    int i=n-2;
    while(--k)
        ans-=d[i--];
    printf("%lld\n",ans);
    return 0;
}

 

相关资讯

  • 那些我们不愿意承认的事

    很久没有见的老朋友,准确的说应该是很久没有见过的老师,一个比我大两岁的老师,我上初中的时候他从高中回来教我了一年。后来又回去上高中,我上高中的时候他上大学,现在我刚大学毕业他创办了公司。昨日一见依然如故,他还是热爱销售,而我却成了纯粹的技术人员。 看到他…

    2015/6/22 13:12:47

学习教程

共有访客发表了评论 网友评论

验证码: 看不清楚?

    立即查看