问题 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 , a i ≤ 100 n≤15,ai≤100 n≤15,ai≤100；
对于70%的数据， n ≤ 103 , a i ≤ 106 n≤103,ai≤106 n≤103,ai≤106；
对于另外10%的数据， k = 1 k=1 k=1；
对于另外10%的数据， k = n k=n k=n；
对于100%的数据， k ≤ n ≤ 105 , a i ≤ 109 k≤n≤105,ai≤109 k≤n≤105,ai≤109，保证ai单调不减。
题意：
将排好序的 n n n个数分成 k k k组求最大价值和最小值，每组的价值是每组的最大值－最小值。
思路：
我们可以看出如果分出一组其实最大价值就是 a n − a 1 a_n-a_1 an−a1
分成两组就是从中间找个断点，最大价值其实就是少了断点的差值最小值，而最小价值就是少了断点的差值最大值。
#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn=2e5+7;#define pii pair<ll,ll>const int mod=1e9+7;ll qpow(ll a,ll b){ll sum=1;while(b){if(b&1)sum=sum*a%mod;b>>=1;a=a*a%mod;}return sum;}ll a[maxn],d[maxn];int main() {ll n,m;cin>>n>>m;for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=1;i<n;i++){d[i]=a[i+1]-a[i];}sort(d+1,d+n);ll sum=0;for(int i=m;i<n;i++) sum+=d[i];ll ans=0;for(int i=n-m;i>=1;i--) ans+=d[i];cout<<ans<<" "<<sum<<endl;return 0;}
