問題 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 long
const 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/226311.html
標籤：其他
上一篇：棋盤問題C++實作與分析
下一篇：2020年csp總結