上海市计算机学会竞赛平台2024年5月月赛丙组城市距离之和
城市距离之和
内存限制: 256 Mb时间限制: 1000 ms
题目描述
设 (x,y)(x,y) 与 (x′,y′)(x′,y′) 是平面上的两个点的坐标,它们之间的城市距离定义为
∣x−x′∣+∣y−y′∣∣x−x′∣+∣y−y′∣
给定 nn 个点,请计算所有点对之间的城市距离之和。
输入格式
- 第一行:单个整数 nn。
- 第二行到第 n+1n+1 行:第 i+1i+1 行有两个整数 xixi 和 yiyi,表示一个点的坐标。
输出格式
- 单个整数:表示所有点对的城市距离之和。
数据范围
- 30%30% 的数据,1≤n≤10001≤n≤1000
- 60%60% 的数据,1≤n≤500001≤n≤50000
- 100%100% 的数据,1≤n≤300,0001≤n≤300,000
- −106≤xi,yi≤106−106≤xi,yi≤106
样例数据
输入:
3
1 1
2 3
1 4
输出:
8
说明:
3 + 3 + 2 = 8
题解:
#include<bits/stdc++.h>
using namespace std;
const int N=300005;
long long x[N],y[N],sum,n,k;
int main(){cin>>n;for(int i=0;i<n;i++){cin>>x[i]>>y[i];}sort(x,x+n);sort(y,y+n);for(int i=n-1,k=n-1;i>=0;i--,k-=2){sum+=k*x[i];sum+=k*y[i];}cout<<sum;return 0;
}
相关文章:
上海市计算机学会竞赛平台2024年5月月赛丙组城市距离之和
城市距离之和 内存限制: 256 Mb时间限制: 1000 ms 题目描述 设 (x,y)(x,y) 与 (x′,y′)(x′,y′) 是平面上的两个点的坐标,它们之间的城市距离定义为 ∣x−x′∣∣y−y′∣∣x−x′∣∣y−y′∣ 给定 nn 个点,请计算所有点对之间的城市距离之和。 …...
穷举vs暴搜vs深搜vs回溯vs剪枝(典型算法思想)—— OJ例题算法解析思路
回溯算法的模版 void backtrack(vector<int>& path, vector<int>& choice, ...) {// 满⾜结束条件if (/* 满⾜结束条件 */) {// 将路径添加到结果集中res.push_back(path);return;}// 遍历所有选择for (int i 0; i < choices.size(); i) {// 做出选择…...
在ubuntu 24.04.2 通过 Kubeadm 安装 Kubernetes v1.31.6
文章目录 1. 简介2. 准备3. 配置 containerd4. kubeadm 安装集群5. 安装网络 calico 插件 1. 简介 本指南介绍了如何在 Ubuntu 24.04.2 LTS 上安装和配置 Kubernetes 1.31.6 集群,包括容器运行时 containerd 的安装与配置,以及使用 kubeadm 进行集群初始…...
基于Python socket库构建的基于 P2P 的文件共享系统示例
基于 P2P 的文件共享系统 实现方式: 使用 Python 的socket库构建 P2P 网络,节点之间通过 TCP 或 UDP 协议进行通信。每个节点维护一个文件列表,并向其他节点广播自己拥有的文件信息。当一个节点需要某个文件时,它会向网络中的其…...
JavaScript 函数重载:灵活应对多场景的编程技巧
在 JavaScript 中,函数重载(Function Overloading)是一个常见的需求。尽管 JavaScript 本身并不支持传统意义上的函数重载(即在同一个作用域内定义多个同名函数,根据参数的不同调用不同的函数),…...
通过 PromptTemplate 生成干净的 SQL 查询语句并执行SQL查询语句
问题描述 在使用 LangChain 和 Llama 模型生成 SQL 查询时,遇到了 sqlite3.OperationalError 错误。错误信息如下: OperationalError: (sqlite3.OperationalError) near "sql SELECT Name FROM MediaType LIMIT 5; ": syntax error [SQL: …...
用大白话解释缓存Redis +MongoDB是什么有什么用怎么用
Redis和MongoDB是什么? Redis:像你家的“小冰箱”,专门存高频使用的食物(数据)。它是基于内存的键值数据库,读写速度极快(每秒超10万次操作)。比如你每次打开手机App,用…...
计算机毕业设计SpringBoot+Vue.js汽车销售网站(源码+文档+PPT+讲解)
温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 作者简介:Java领…...
【0010】HTML水平线标签详解
如果你觉得我的文章写的不错,请关注我哟,请点赞、评论,收藏此文章,谢谢! 本文内容体系结构如下: 一、水平线标签概述 在HTML中,<hr>标签用于在网页上插入一条水平线,其主要…...
FastExcel与Reactor响应式编程深度集成技术解析
一、技术融合背景与核心价值 在2025年企业级应用开发中,大规模异步Excel处理与响应式系统架构的结合已成为技术刚需。FastExcel与Reactor的整合方案,通过以下技术协同实现突破性性能: 内存效率革命:FastExcel的流式字节操作与Re…...
Netty是如何实现零拷贝的?
大家好,我是锋哥。今天分享关于【Netty是如何实现零拷贝的?】面试题。希望对大家有帮助; Netty是如何实现零拷贝的? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 Netty是一个高性能的Java网络应用框架,它…...
【大模型➕知识图谱】大模型结合医疗知识图谱:解锁智能辅助诊疗系统新范式
【大模型➕知识图谱】大模型结合医疗知识图谱:解锁智能辅助诊疗系统新范式 大模型结合医疗知识图谱:解锁智能辅助诊疗系统新范式引言一、系统架构1.1 系统架构图1.2 架构模块说明1.2.1 用户输入1.2.2 大模型(语义理解与意图识别)1.2.3 Agent(问题解析与任务分配)1.2.4 问…...
Spring Boot @Component注解介绍
Component 是 Spring 中的一个核心注解,用于声明一个类为 Spring 管理的组件(Bean)。它是一个通用的注解,可以用于任何层次的类(如服务层、控制器层、持久层等)。通过 Component 注解,Spring 会…...
MulFS-CAP: Multimodal Fusion-supervisedCross-modal
一种用于无注册红外-可见图像融合的单阶段框架。与传统的两阶段方法不同,MulFS-CAP结合了隐式注册和融合,简化了处理流程并增强了实用性。该方法使用共享的浅层特征编码器,同时进行特征对齐和图像融合。通过引入可学习的模态字典,…...
WordPress多语言插件GTranslate
GTranslate是一个免费的WordPress多语言插件,它允许您将网站内容翻译成多种语言。这个插件提供了一个简单易用的界面,让您可以在WordPress后台直接进行翻译操作。以下是GTranslate插件的一些主要特点: 免费使用:GTranslate插件完…...
wordpress子分类调用父分类名称和链接的3种方法
专为导航而生,在wordpress模板制作过程中常常会在做breadcrumbs导航时会用到,子分类调用父分类的名称和链接,下面这段简洁的代码,可以完美解决这个问题。 <?php echo get_category_parents( $cat, true, » ); ?…...
Prometheus + Grafana 监控
Prometheus Grafana 监控 官网介绍:Prometheus 是一个开源系统 监控和警报工具包最初由 SoundCloud 构建。自 2012 年成立以来,许多 公司和组织已经采用了 Prometheus,并且该项目具有非常 活跃的开发人员和用户社区。它现在是一个独立的开源…...
初学STM32之简单认识IO口配置(学习笔记)
在使用51单片机的时候基本上不需要额外的配置IO,不过在使用特定的IO的时候需要额外的设计外围电路,比如PO口它是没有内置上拉电阻的。因此若想P0输出高电平,它就需要外接上拉电平。(当然这不是说它输入不需要上拉电阻,…...
springboot2.7.18升级springboot3.3.0遇到的坑
druid的警告,警告如下: 运行警告2025-02-28T09:20:31.28508:00 WARN 18800 --- [ restartedMain] trationDelegate$BeanPostProcessorChecker : Bean com.alibaba.druid.spring.boot3.autoconfigure.stat.DruidSpringAopConfiguration of type [com.a…...
gtest 和 gmock讲解
Google Test(gtest)和 Google Mock(gmock)是 Google 开发的用于 C 的测试框架和模拟框架,以下是对它们的详细讲解: Google Test(gtest) 简介 Google Test 是一个用于 C 的单元测试框…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
Mysql故障排插与环境优化
前置知识点 最上层是一些客户端和连接服务,包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念,为通过安全认证接入的客户端提供线程。同样在该层上可…...
