首页 > 其他 > 详细

G - Christmas Play

时间:2014-08-20 11:47:56      阅读:477      评论:0      收藏:0      [点我收藏+]

Description

My kid‘s kindergarten class is putting up a Christmas play.  (I hope he gets the lead role.)  The kids are all excited, but the teacher has a lot of work.  She has to produce costumes for a scene with K soldiers.  She wants to buy all the costumes in the same size, allowing for some small amount of length alteration to be done by the kids‘ parents later.  So she has taken all the kids‘ height measurements.  Can you help her select K kids from her class of N to play the soldier role, such that the height difference between the tallest and shortest in the group is minimized, and alternations will be easiest?  Tell her what this minimum difference is.
 
 
INPUT
The first line contains the number of test cases T. T test cases follow each containing 2 lines.
 
The first line of each test case contains 2 integers N and K.
The second line contains N integers denoting the height of the N kids.
 
OUTPUT
Output T lines, each line containing the required answer for the corresponding test case.
 
CONSTTRAINTS
T <= 30
1 <= K <= N <= 20000
1 <= height <= 1000000000
 
SAMPLE INPUT
3
3 1
2 5 4  
3 2
5 2 4  
3 3
2 5 4  
 
 
SAMPLE OUTPUT
0
1
3
 
EXPLANATION
In the first test case, the teacher needs to only select 1 kid and hence she can choose any kid since the height difference is going to be 0.
In the second test case, the teacher can choose kids with height 4 and 5.
In the third test case, the teacher is forced to choose all 3 kids and hence the answer = 5-2 = 3

 

题意:3 2   三个人   间隔为2
        5 2 4  三个人的身高    求间隔为2的最小身高差
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

int main()
{
    int t,n,d;
    int a[20002];
    while(~scanf("%d",&t))
    
    while(t--)
    {
        scanf("%d%d",&n,&d);
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        int sum=1000000001;
        for(int i=0; i<n-d+1; i++)
        {
            //cout<<a[i]<<‘ ‘<<a[i+d-1]<<"!!!!!!!!"<<endl;
            if(sum>(a[i+d-1]-a[i]))
                sum=(a[i+d-1]-a[i]);
        }
       printf("%d\n",sum);
    }
    return 0;
}

 

G - Christmas Play,布布扣,bubuko.com

G - Christmas Play

原文:http://www.cnblogs.com/zhangying/p/3923957.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!