NC200005. 雷顿女士与分队（hard version）
描述
输入描述
第一行输入一个T(1<=T<=10)表示数据组数。
接下来T组数据。
然后输入n，k(1<=n<=100000,1<=k<=n)。
然后接下来一行输入n个数字，第i个数字表示标号为i的选手的实力(
)。
输出描述
对于每组数据，请输出一个数字表示答案。
请注意，行末不要输出多余空格。
示例1
输入:
6 5 1 1 2 3 1 1 5 2 1 2 3 1 1 5 3 1 2 3 1 1 5 4 1 2 3 1 1 5 5 1 2 3 1 1 9 3 1 1 2 2 1 10 10 10 10
输出:
0 1 2 2 2 8
Python3 解法, 执行用时: 1612ms, 内存消耗: 21592K, 提交时间: 2022-04-08 16:43:36
t= int(input())
for _ in range(t):
n,k=map(int,input().split())
dp=[0,0]
ls = list(map(int,input().split()))
ls.sort()
su=0
if n<2*k:
print(ls[-1]-ls[0])
continue
for i in range(2*k-2):
su+=ls[i+1]-ls[i]
dp.append(su)
# print(dp)
for i in range(2*k,n+1):
if i % k==0:
dp.append(dp[i-k]+ls[i-1]-ls[i-k])
else:
dp.append(min(dp[i-k]+ls[i-1]-ls[i-k],dp[i-1]+ls[i-1]-ls[i-2]))
# print(ls[i-k],ls[i-1])
# print(dp)
print(dp[n])
C++11(clang++ 3.9) 解法, 执行用时: 207ms, 内存消耗: 2028K, 提交时间: 2019-12-13 19:23:04
#include <stdio.h>
#include <algorithm>
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
long long d[100005],a[100005];
int main()
{
int t,n,k;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=k-1;i++)d[i]=INF;
for(int i=1;i<=n;i++)
{
if(i%k)
{
if(i>k)
d[i]=min(d[i-k]+a[i]-a[i-k+1],d[i-1]+a[i]-a[i-1]);
}
else d[i]=d[i-k]+a[i]-a[i-k+1];
}
printf("%lld\n",d[n]);
}
}