Blog·Tanky WooABOUTRSS

HDOJ 2523 SORT AGAIN

29 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=2523

嘿嘿,看见MiYu就这题没过,于是去做下试试。。。

结果~~~1次AC,hoho。

只做了一点优化,就是判断差值的最大值。

 // Author: Tanky Woo
// HDOJ 2523
// Accepted 2523 93MS 188K 777B C++ Tanky Woo 
#include 
#include 
#include 
using namespace std;
int hash[2010];
int arr[1005];

int main()
{
    int nCases;
    int nNum, nKth;
    scanf("%d", &nCases;);
    while(nCases--)
    {
        memset(hash, 0, sizeof(hash));
        memset(arr, 0, sizeof(arr));
        scanf("%d %d", &nNum;, &nKth;);
        for(int i=0; i<nNum; ++i)
            scanf("%d", &arr[i]);
        sort(arr, arr+nNum);
        int _max = arr[nNum-1] - arr[0];   //做了一点优化
        for(int i=0; i<nNum; ++i)
            for(int j=i+1; j<nNum; ++j)
                hash[abs(arr[i]-arr[j])] = 1;
        int cnt = 0;
        for(int i=0; i<_max+5; ++i)
        {
            if(hash[i])
                cnt++;
            if(cnt == nKth)
            {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;

}