题意:给你一个长度为\(n\)的升序序列,将这个序列分成\(k\)段,每一段的值为最大值和最小值的差,求\(k\)段值的最小和.
题解:其实每一段的最大值和最小值的差,其实就是这段元素的差分和,因为是升序,我们可以先求出差分数组,然后再对差分数组排序,因为我们可以分成\(k\)段,所以会有\(k-1\)个断开的'缝隙',也就是说两个段之间的差分是不用贡献给答案的,所以我们直接取前\(n-k+1\)个差分和就可以了.
-
代码:
int n,k;
int a[N];
int c[N]; int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;++i) cin>>a[i]; for(int i=2;i<=n;++i) c[i-1]=a[i]-a[i-1]; sort(c+1,c+n); int ans=0;
for(int i=1;i<n-k+1;++i) ans+=c[i]; cout<<ans<<endl; return 0;
}
相关文章
- Educational Codeforces Round 62 (Rated for Div. 2)E(染色DP,构造,思维,组合数学)
- Educational Codeforces Round 69 (Rated for Div. 2)D(DP,思维)
- Educational Codeforces Round 69 (Rated for Div. 2)
- C. Playlist Educational Codeforces Round 62 (Rated for Div. 2) 贪心+优先队列
- C. Magic Ship Educational Codeforces Round 60 (Rated for Div. 2)
- Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array (简单DP)
- Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array 分类讨论连续递推dp
- Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array(动态规划.递推)
- Educational Codeforces Round 62 (Rated for Div. 2)E(染色DP,构造,思维,组合数学)
- Educational Codeforces Round 61 (Rated for Div. 2)-C. Painting the Fence 前缀和优化