列表

详情

NC51064. Euclidean Distance

描述

Bobo has a point A in the n dimension real space , whose coodinate is where a_i and m are both integers. He wants to find another point meeting the following requirements.

* . That is, they are real numbers.
*
*
* The (squared) Euclidean distance between P and A, which is , is minimized.

It can be proved the minimum is always a rational number. Print the squared distance in fraction. Note to print an integer n as `n` instead of `n/1`.

输入描述

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains two integers n and m.
The second line contains n integers .

* 
* 
* 
* The sum of n does not exceed .

输出描述

For each test case, print a fraction which denotes the result.

示例1

输入: 

1 1
0
2 3
1 2
3 10
1 -2 3

输出: 

1
0
16/75

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 116ms, 内存消耗: 2748K, 提交时间: 2019-07-18 21:27:21 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4+5;
ll a[N],ans,m,n;
int solve(){
	ans=0;for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	sort(a+1,a+1+n,greater<int>());ll nd=0;
	for(int i=1;i<=n;i++){
		if(i<n&&(a[i]-a[i+1])*i+nd<=m) nd+=(a[i]-a[i+1])*i;
		else{
			ans=(m-nd-i*a[i])*(m-nd-i*a[i]);
			for(int j=i+1;j<=n;j++)ans+=i*a[j]*a[j];
			ll d,p=i*m*m;if(ans==0)return puts("0");
			d=__gcd(ans,p);ans/=d;p/=d;
			if(p==1)printf("%lld\n",ans);
			else printf("%lld/%lld\n",ans,p);
			return 0;
		}
	}
	return 0;
}
int main(){
	while(scanf("%lld%lld",&n,&m)!=EOF)solve();
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 119ms, 内存消耗: 2936K, 提交时间: 2019-07-19 14:05:08 

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 10010
int n,m;
ll a[N],s2[N];
int main(){
	int i,j;
	while(~scanf("%d%d",&n,&m)){
		ll s=0;
		for(i=1;i<=n;i++)scanf("%lld",&a[i]),s+=a[i];
		sort(a+1,a+1+n);
		for(i=1;i<=n;i++)s2[i]=s2[i-1]+a[i]*a[i];
		for(i=1;i<=n;i++){
			if(a[i]*(n-i+1)-s+m>=0)break;
			s-=a[i];
		}
		ll fz=s2[i-1]*(n-i+1)+(s-m)*(s-m),fm=1LL*m*m*(n-i+1);
		ll g=__gcd(fz,fm);
		fz/=g;fm/=g;
		if(fm==1)printf("%lld\n",fz);
		else printf("%lld/%lld\n",fz,fm);
	}
	return 0;
}

上一题

© 2025 nowcoder.com