Description


A先生有很多双筷子。确切的说应该是很多根，因为筷子的长度不一，很难判断出哪两根是一双的。这天，A先生家里来了K个客人，A先生留下他们吃晚饭。加上A先生，A夫人和他们的孩子小A，共K+3个人。每人需要用一双筷子。A先生只好清理了一下筷子，共N根，长度为T1，T2，T3，……，TN。现在他想用这些筷子组合成K+3双，使每双的筷子长度差的平方和最小。（怎么不是和最小？？这要去问A先生了，呵呵）


Input


共有两行，第一行为两个用空格隔开的整数，表示N，K（1≤N≤100，0<K<50），第二行共有N个用空格隔开的整数。


Output

仅一行。如果凑不齐K+3双，输出-1，否则输出长度差平方和的最小值。

Sample Input

10 1
1 1 2 3 3 3 4 6 10 20


Sample Output

5


Hint


第一双 1 1

第二双 2 3

第三双 3 3

第四双 4 6

(1-1)^2+(2-3)^2+(3-3)^2+(4-6)^2=5

不是很理解什么意思？

试试这个

#include <stdio.h>
#include <math.h>

void bubble(int a[],int n);
int  mincount(int a[],int num_people);

int main(int argc, char *argv[])
{
    int t[100];
    int n,k;
    int num_people;
    int i;
    int result;
    printf("please input number of n and k :\n");
    scanf("%d %d",&n,&k);
    printf("please  n members of array:\n");
    for(i=0;i<n;i++)
    scanf("%d",&t[i]);


    num_people=k+3;

    if(n<(k+3)*2)
    {
        printf("-1 \n");
        return 0;
    }

    bubble(t,n);

   result=mincount(t,num_people);
       printf("%d\n",result);
    return 0;
}



void bubble(int a[],int n)
{
    int i,j;
    int temp;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n-i-1;j++)
        {
            if (a[j]>a[j+1])
            {
                temp=a[j+1];
                a[j+1]=a[j];
                a[j]=temp;
            }
        }
    }
}


int  mincount(int a[],int num_people)
{
    int i;
    int temp;
    int sum=0;

    for(i=0;i<num_people;i++)
    {
     temp=a[2*i]-a[2*i+1];
         temp=temp*temp;
          sum=sum+temp;
    }

    return sum;

}

[ 本帖最后由 NOMIPS 于 2010-6-5 17:25 编辑 ]

什么呀~

看样子是对的，简单的贪心，/

这题无论如何贪心都过不了全部的解，如果你觉得是贪心只能说贪心在部分条件下可行，请好好学习一下DP再下结论