UPC——Heartlessly 的魔法石（排序）

问题 G: Heartlessly 的魔法石

时间限制: 1 Sec 内存限制: 128 MB

题目描述

Heartlessly 有 n 个魔法石，每个魔法石都有对应的魔法值（用正整数 a i 表示）。Heartlessly把它们按魔法值从小到大排成一行，并分成 k 组，每组魔法石产生的能量为组中最大的魔法值减去最小的魔法值。你能求出这些魔法石产生的最小能量和最大能量分别是多少吗？

输入

第一行，输入两个正整数n,k，分别表示魔法石数量和分组数量。

第二行，输入正整数a1∼an，表示每个魔法石对应的魔法值。

输出

第一行，输出最小能量和最大能量，中间用空格隔开。

样例输入 Copy

8 3

2 3 5 7 11 13 17 19

样例输出 Copy

9 14

提示

样例解释

最小值：[2,3,5,7],[11,13],[17,19]

最大值：[2],[3,5],[7,11,13,17,19]

对于40%的数据，n≤15,ai≤100；

对于70%的数据，n≤103,ai≤106；

对于另外10%的数据，k=1；

对于另外10%的数据，k=n；

对于100%的数据，k≤n≤105,ai≤109，保证ai单调不减。

思路：

无论怎么划分，第一个数和最后一个数是必选的，再来考虑其余的数对答案的贡献。分组后第i组的最后一个数x和第i+1组的第一个数y必定是相邻的，这两个数对答案的贡献x-y。

因为第一个数和最后一个数已经被选了，只需要再选k-1个相邻的两个数就好。

只需要对每两个数都计算出贡献，排序后取前k-1小和前k-1大即可。

代码：

const int maxn=1e5+100;
int a[maxn],n,k;
ll b[maxn];
int main()
{
    n=read(),k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<n;i++) b[i]=a[i]-a[i+1];
    sort(b+1,b+n);
    ll maxx=-a[1]+a[n],minn=a[n]-a[1];
    for(int i=1,j=n-1;i<=k-1;i++,j--)
        minn+=b[i],maxx+=b[j];
    cout<<minn<<" "<<maxx<<endl;
    return 0;
}