篮桥云课-摆玩具

思维好题

一开始掉进了二分的陷阱，发现看看逐个位置的差，我们要分成k段就是要取消k-1个最大的逐差

然后将剩余的加起来就可以了

因为本体保证是从小到大给出的 这一点保证了答案的正确性，自己没想出来 还是太菜了

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n,k;
int w[N];
vector<int>s;
using ll = long long;
ll res;
int main()
{cin>>n>>k;for(int i=1;i<=n;i++)cin>>w[i];for(int i=2;i<=n;i++)s.push_back(w[i]-w[i-1]);sort(s.begin(),s.end(),greater<>());k = k-1;for(auto &t:s){if(!k)break;t = 0;k--;}for(auto t:s)res+=t;cout<<res;
}