Codeforces Round 882 (Div. 2)
A. The Man who became a God
标签
greedy sortings
思路
- 记 \(A\) 为 \(|a_{i}-a_{i+1}|\) 的前 \(k-1\) 大之和，则答案即为\((\sum\limits_{1}^{n-1}|a_{i}-a_{i+1}|)-A\)。
- 时间复杂度为 \(\mathcal O(tn\log n)\)。
代码
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=110;
int t,n,k,a[maxn],ans=0;
bool cmp(int a,int b) {return a>b;}
int main ()
{
scanf("%d",&t);
while(t--)
{
ans=0;
scanf("%d%d",&n,&k);
int x,y; scanf("%d",&x);
for(int i=1;i<n;i++)
{
scanf("%d",&y);
a[i]=abs(y-x),x=y;
}
sort(a+1,a+n,cmp);
for(int i=k;i<n;i++)
ans+=a[i];
printf("%d\n",ans);
}
return 0;
}