链接：https://www.nowcoder.com/acm/contest/89/A
来源：牛客网
- 1.题目描述
The Great Wall story of Meng Jiangnv’s Bitter Weeping happened during the Qin Dynasty (221BC- 206BC). Meng jiangnv was a beauty in the Qin Dynasty, and she lived happily with her husband. At that time, Emperor Qin Shihuang (the first emperor of Qin) announced to build the Great Wall. And the officials suddenly broke in their happy life and took Meng’s husband away to build the wall. Because of the missing for her husband, she decided to set off to look for her husband. After a long journey, finally she reached the foot of the Great Wall at the present Shanhaiguan Pass. Upon her arrival, a bad news came to her, however, her husband had already died of exhaustion and was buried into the Great Wall! Meng could not help crying. She sat on the ground and cried and cried. Suddenly with a tremendous noise, a 400 kilometer-long (248-mile-long) section of the wall collapsed over her bitter wail.
Today, Qin Shihuang gets N stones. The height of the ith stone is Ai. He will use all these stones to rebuild the Great Wall. In order to make the Great Wall more sturdy, the prime minister Li Si proposes a formula to calculate the “weakness” of the reconstructed Great Wall
The Bi is the height of the ith stone in the reconstructed Great Wall, and the K is provided by Li Si.
For example, Qin Shihuang gets 5 stones. The height of these stones are [5,3,2,4,1], and the K is 2. There are 120 different ways to rebuild the Great Wall. The following figures show the two solutions:
The weakness of left figure and right figure are 4 and 11, respectively.
Now, Li Si wants to know the minimum value of “weakness”. Li Si is too old to calculate the answer quickly, so he asks you for help.
输入描述:
The first line contains an integer T, where T is the number of test cases. T test cases follow.
For each test case, the first line contains two integers N and K, where N is the number of stones and K is a variable which provided by Li Si.
The second line contains N integers A1, A2, … , AN, where Ai is the height of the ith stone that QinShiHuang gets.
• 1 ≤ T ≤ 50.
• 1 ≤ N ≤ 103.
• 1 ≤ K ≤ N.
• 1≤ Ai ≤104.
输出描述:
For each test case, print one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the minimum value of “weakness”.
示例1
输入
2
5 2
1 2 3 4 5
5 3
1 3 2 2 7
输出
Case #1: 4
Case #2: 7
备注:
For the first case, one of the best ways is [1,2,3,4,5], weakness = (2−1)+(3−2)+(4−3)+(5−4) = 4.
For the second case, one of the best ways is [7,3,2,2,1], weakness = (7−2)+(3−2)+(2−1) = 7. - 2.题目分析
关键就是着weakness的计算公式，它计算的是所有a[i+k-1]-a[i]的值，同时a[i+k-1]（最大）-a[i]（最小），所以做法就是先递增排序，累加所有a[i+k-1]-a[i]的值，输出结果就是答案 - 3.代码如下
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 100;
char str1[2000], s2[2000];
int dp[105];
int ap[105], bp[105];
const int MAXN= 1000005;
int a[10005];
int main()
{
int T,d=1;
scanf("%d",&T);
while(T--)
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
int res=0;
for(int i=0;i+k-1<n;i++)
{
res+=a[i+k-1]-a[i];
}
printf("Case #%d: %d
",d++,res);
}
return 0;
}