问题 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; }
