NC16788. 黑妹的游戏V
描述
输入描述
第一行一个整数T表示数据组数。(1 ≤ T ≤ 10)
对于每组数据：
第一行两个整数n和k，分别表示棋子的个数和组成超级棋子的棋子个数。(1 ≤ k ≤ n ≤ 100)
下面n行每行两个整数 xi，yi表示棋子的位置。(-109 ≤ xi, yi ≤ 109)
输出描述
对于每组数据输出一行表示答案。
示例1
输入:
1 3 2 2 4 1 2 3 5
输出:
2
C++14(g++5.4) 解法, 执行用时: 327ms, 内存消耗: 352K, 提交时间: 2019-02-06 14:48:27
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=105;
int T,n,k,x[maxn],y[maxn];
ll a[maxn];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]);
ll ans=4e18;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
for(int l=1;l<=n;l++)a[l]=(ll)abs(x[l]-x[i])+(ll)abs(y[l]-y[j]);
sort(a+1,a+n+1);
ll res=0;
for(int l=1;l<=k;l++)res+=a[l];
ans=min(ans,res);
}
printf("%lld\n",ans);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 309ms, 内存消耗: 604K, 提交时间: 2020-03-11 10:24:25
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=105;
int T,n,k,x[maxn],y[maxn];
ll a[maxn];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
ll ans=4e18;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
for(int l=1;l<=n;l++) a[l]=(ll)abs(x[l]-x[i])+(ll)abs(y[l]-y[j]);
sort(a+1,a+n+1);
ll res=0;
for(int l=1;l<=k;l++) res+=a[l];
ans=min(ans,res);
}
printf("%lld\n",ans);
}
return 0;
}