POJ 3244 Difference between Triplets 公式转换

2024-04-23 19:48

本文主要是介绍POJ 3244 Difference between Triplets 公式转换,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:两个三元组(x1,y1,z1)(x2,y2,z2)的距离如下定义

D = max {x1 − x2, y1 − y2, z1 − z2} − min {x1 − x2, y1 − y2, z1 − z2}

现在给你n个三元组,让你求出任意两个三元组的距离之和。

 

题解:公式转换非常有用,必须引起重视

先简化一下模型:

a = x1-x2, b=y1-y2, c=z1-z2

D = max {a,b,c} − min {a,b,c}

这样的话 D = (|a-b|+|b-c|+|c-a|)/2。在数轴上画一下即可看清楚

D = (|(x1-x2)-(y1-y2)|+|(y1-y2)-(z1-z2)|+|(z1-z2)-(x1-x2)|)/2

D = (|(x1-y1)-(x2-y2)|+|(y1-z1)-(y2-z2)|+|(z1-x1)-(z2-x2)|)/2

再令 a1=x1-y1, b1=y1-z1, c1=z1-x1

那么 D = (|a1-a2|+|b1-b2|+|c1-c2|)/2

到这一步其实还是比较难算的,因为绝对值不好去掉

由于每个三元组需要与其它n-1个三元组计算一次

那么每个a,b,c都要与其他三元组的a,b,c计算一次

那么不妨将所有的a,b,c排序

这样一来排在ai之前的a0,a1···都比ai小,那么ai就要贡献i+ai

而排在ai之后的所有值都比ai大,那么ai就要贡献n-1-i-ai

所以ai总的贡献是 [i-(n-1-i)] * ai = [i+i-n+1] * ai

对于b,c的计算同理。 

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200000
int a[MAXN], b[MAXN], c[MAXN];
int main()
{
int x, y, z, n;
while ( scanf("%d",&n) && n )
{
for ( int i = 0; i < n; i++ )
{
scanf("%d%d%d",&x,&y,&z);
a[i] = x-y;
b[i] = y-z;
c[i] = z-x;
}
sort(a,a+n);
sort(b,b+n);
sort(c,c+n);
__int64 ret = 0;
for ( __int64 i = 0; i < n; i++ )  //注意做乘法的时候数据超出int范围
{
ret += (i+i-n+1) * a[i];
ret += (i+i-n+1) * b[i];
ret += (i+i-n+1) * c[i];
}
printf("%I64d\n",ret/2);
}
return 0;
}


 

这篇关于POJ 3244 Difference between Triplets 公式转换的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/929720

相关文章

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

Java实现XML与JSON的互相转换详解

《Java实现XML与JSON的互相转换详解》这篇文章主要为大家详细介绍了如何使用Java实现XML与JSON的互相转换,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. XML转jsON1.1 代码目的1.2 代码实现2. JSON转XML3. JSON转XML并输出成指定的

利用Python实现添加或读取Excel公式

《利用Python实现添加或读取Excel公式》Excel公式是数据处理的核心工具,从简单的加减运算到复杂的逻辑判断,掌握基础语法是高效工作的起点,下面我们就来看看如何使用Python进行Excel公... 目录python Excel 库安装Python 在 Excel 中添加公式/函数Python 读取

Java实现将Markdown转换为纯文本

《Java实现将Markdown转换为纯文本》这篇文章主要为大家详细介绍了两种在Java中实现Markdown转纯文本的主流方法,文中的示例代码讲解详细,大家可以根据需求选择适合的方案... 目录方法一:使用正则表达式(轻量级方案)方法二:使用 Flexmark-Java 库(专业方案)1. 添加依赖(Ma

Java实现将byte[]转换为File对象

《Java实现将byte[]转换为File对象》这篇文章将通过一个简单的例子为大家演示Java如何实现byte[]转换为File对象,并将其上传到外部服务器,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言1. 问题背景2. 环境准备3. 实现步骤3.1 从 URL 获取图片字节数据3.2 将字节数组

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.