这篇博客是从旧博客 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;
}