Problem 1015 - Requirements
分析
试着写的时候加上空格,看会不会好看些
分析
不知为什么前一段时间看不到这题,现在突然出现了
题目给出n个点,每个点有一个五维的坐标(x1,x2,x3,x4,x5),求任意两点间最大的“距离”,此处两点距离定义为abs(x1-y1)+....abs(x5-y5)
由于n范围会达到10w,所以列举出所有点计算是不行的,由于此处距离的定义是一个比较典型的数学表达式,可以从此处入手:
距离由5个绝对值符号加起来的,我们考虑去掉绝对值,这样就有32种可能性
第一种,原本全部是正数:(x1-y1)+...(x5-y5)=(x1+x2+..x5)-(y1+y2+..y5)
第二种,除了第二个,全部是正数:(x1-y1)+(y2-x2)+(x3-y3)+(x4-y4)+(x5-y5)=(x1-x2+x3+x4+x5)-(y1-y2+y3+y4+y5)
......
第三十二中,(y1-x1)+...(y5-x5)=(-x1-x2-x3-x4-x5)-(-y1-y2-y3-y4-y5)
同时,最终答案=以上三十二个答案中的最大值
所以,对于每一种情况,直接求出n个点的此种形式的最大值和最小值,取差,32个差中最大值即为答案
题目给出n个点,每个点有一个五维的坐标(x1,x2,x3,x4,x5),求任意两点间最大的“距离”,此处两点距离定义为abs(x1-y1)+....abs(x5-y5)
由于n范围会达到10w,所以列举出所有点计算是不行的,由于此处距离的定义是一个比较典型的数学表达式,可以从此处入手:
距离由5个绝对值符号加起来的,我们考虑去掉绝对值,这样就有32种可能性
第一种,原本全部是正数:(x1-y1)+...(x5-y5)=(x1+x2+..x5)-(y1+y2+..y5)
第二种,除了第二个,全部是正数:(x1-y1)+(y2-x2)+(x3-y3)+(x4-y4)+(x5-y5)=(x1-x2+x3+x4+x5)-(y1-y2+y3+y4+y5)
......
第三十二中,(y1-x1)+...(y5-x5)=(-x1-x2-x3-x4-x5)-(-y1-y2-y3-y4-y5)
同时,最终答案=以上三十二个答案中的最大值
所以,对于每一种情况,直接求出n个点的此种形式的最大值和最小值,取差,32个差中最大值即为答案
试着写的时候加上空格,看会不会好看些
程序代码:
#include <stdio.h> #include <stdlib.h> double a[100000][5],max,min,ans,now; int n,i,j,k; int main() { while (scanf("%d",&n) != EOF) { for (i = 0; i < n; i++) for ( j = 0; j < 5; j++) scanf("%lf",&a[ i ][ j ]); ans=0.0; for (k = 0; k < 32; k++) { max = -1e10; min = 1e10; for (i = 0; i < n; i++) { now = 0; for (j = 0; j < 5; j++) if ((1 << j) & k) now = now + a[ i ][ j ]; else now = now - a[ i ][ j ]; if (max < now) max = now; if (min > now) min = now; } if (ans < max - min) ans = max - min; } printf("%.2lf\n",ans); } }