[Daimayuan] 奶牛集会(C++,线段树)

news/2024/4/17 10:02:37

题目描述

约翰的 n n n 头奶牛每年都会参加“哞哞大会”。

哞哞大会是奶牛界的盛事。集会上的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。

它们参加活动时会聚在一起,第 i i i 头奶牛的坐标为 x i x_i xi,没有两头奶牛的坐标是相同的。

奶牛们的叫声很大,第 i i i 头和第 j j j 头奶牛交流,会发出 m a x { v i , v j } × ∣ x i − x j ∣ max\{v_i,v_j\}×|x_i−x_j| max{vi,vj}×xixj 的音量,其中 v i v_i vi v j v_j vj 分别是第 i i i 头和第 j j j 头奶牛的听力。

假设每对奶牛之间同时都在说话,请计算所有奶牛产生的音量之和是多少。

输入格式

1 1 1 行:单个整数 n n n 1 ≤ n ≤ 3 × 1 0 4 1≤n≤3×10^4 1n3×104

2 2 2 行到第 n + 1 n+1 n+1 行:第 i + 1 i+1 i+1 行有两个整数 v i v_i vi x i x_i xi 1 ≤ v i , x i ≤ 3 × 1 0 4 1≤v_i,x_i≤3×10^4 1vi,xi3×104)。

输出格式

输出单个整数,表示所有奶牛产生的音量之和。

样例输入

4
3 1
2 5
2 6
4 3

样例输出

57

补充说明

原题:[USACO04OPEN] MooFest G。

虽然可以使用 O ( N 2 ) O(N^2) O(N2) 的模拟通过本题,但为了保证其趣味性,建议使用 分治树状数组

双倍经验: O ( N 2 ) O(N^2) O(N2) 过不去的 加强版。

解题思路

读完题后想了想,好像找不到什么子结构可以用来优化算法。

所以直接模拟:

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
using namespace std;
const int max_n = 3e4;long long pos[max_n], vol[max_n];int main() {int n, i, j;scanf("%d", &n);long long ans = 0;for (i = 0; i < n; i++) {scanf("%lld%lld", vol + i, pos + i);for (j = 0; j < i; j++) {ans += max(vol[i], vol[j]) * abs(pos[i] - pos[j]);}}printf("%lld\n", ans);return 0;
}

噫,好了,我过了。

然后我们尝试优化算法,使它能够通过加强版数据。

之前算法低效的根本原因是每次只能处理一对奶牛之间的交流,我们需要想办法批量处理。

对于计算公式 m a x { v i , v j } × ∣ x i − x j ∣ max\{v_i,v_j\}×|x_i−x_j| max{vi,vj}×xixj,如果在指定奶牛群中, i i i号奶牛的音量最大,我们就可以进行批量处理了。

所以我们将奶牛按音量排序,然后逐个加入奶牛群中。

每加入一头奶牛,累计它和其他所有奶牛的交流音量。

最后,加强版AC代码如下:

#include <cstdio>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
const int max_n = 5e4;struct cow { long long pos, vol; }cows[max_n + 1];
long long tree1[max_n * 4], tree2[max_n * 4];	//tree1维护奶牛的位置和,tree2维护奶牛的数量void update(int idx, int l, int r, int pos, long long val, long long tree[]) {/* 在tree所维护的数组的pos位置加上val */if (l == r) {tree[idx] += val;return;}int m = l + r >> 1;if (pos <= m) update(idx << 1, l, m, pos, val, tree);else update((idx << 1) + 1, m + 1, r, pos, val, tree);tree[idx] = tree[idx << 1] + tree[(idx << 1) + 1];
}long long query(int idx, int l, int r, int L, int R, long long tree[]) {/* 查询[L,R]区间和 */if (L <= l && r <= R) {return tree[idx];}int m = l + r >> 1;long long ret = 0;if (L <= m) ret += query(idx << 1, l, m, L, R, tree);if (R > m) ret += query((idx << 1) + 1, m + 1, r, L, R, tree);return ret;
}int main() {int n, i, j;scanf("%d", &n);//cin >> n;for (i = 1; i <= n; i++) {scanf("%lld%lld", &(cows[i].vol), &(cows[i].pos));//cin >> cows[i].vol >> cows[i].pos;}sort(cows + 1, cows + n + 1, [](cow c1, cow c2) {return c1.vol < c2.vol;});long long ans = 0;long long front_sum, back_sum, front_num, back_num;for (i = 1; i <= n; i++) {front_sum = query(1, 1, max_n, 1, cows[i].pos, tree1);back_sum = query(1, 1, max_n, cows[i].pos, max_n, tree1);//对于相同位置,距离为0,重复计数无影响front_num = query(1, 1, max_n, 1, cows[i].pos, tree2);back_num = query(1, 1, max_n, cows[i].pos, max_n, tree2);//对于相同位置,距离为0,重复计数无影响ans += cows[i].vol * (front_num * cows[i].pos - front_sum + back_sum - back_num * cows[i].pos);update(1, 1, max_n, cows[i].pos, cows[i].pos, tree1);update(1, 1, max_n, cows[i].pos, 1LL, tree2);}printf("%lld\n", ans);return 0;
}

http://www.ppmy.cn/news/433197.html

相关文章

基于机器学习算法:朴素贝叶斯和SVM 分类-垃圾邮件识别分类系统(含Python工程全源码)

目录 前言总体设计系统整体结构图系统流程图 运行环境Python 环境安装pytesseract注册百度云账号 模块实现1. 数据模块2. 模型构建3. 附加功能 系统测试1. 文字邮件测试准确率2. 网页测试结果 工程源代码下载其它资料下载 前言 本项目采用朴素贝叶斯和支持向量机&#xff08;S…

2022第三届全国大学生网络安全精英赛练习题(全部试题)

全国大学生网络安全精英赛 文章目录 全国大学生网络安全精英赛200400500600700800 1、某公司技术人员利于自己的技术入侵了某电商数据库&#xff0c;将其中的用 户数据下载后在暗网中进行售卖&#xff0c;该行为的处置最适用的是以下那部法律?( ) A.刑法 B.网络安全法 C.电子签…

图片转excel表格算法之霍夫变换法原理浅析

大家伙都知道&#xff0c;图片转excel表格是金鸣识别中一项非常重要的功能&#xff0c;金鸣识别的OCR在识别图片中的表格时&#xff0c;会用到一种叫霍夫变换法的算法&#xff0c;那这个算法到底是怎么回事&#xff1f;它的原理又是什么呢&#xff1f; 一、霍夫变换法的概念 …

一道北大强基题背后的故事(四)——数学之美,美在哪里?

早点关注我&#xff0c;精彩不错过&#xff01; 在前面文章中&#xff0c;我们重点聊了[((1 sqrt(5)) / 2) ^ 12]这道题可能的弯路&#xff0c;出题思路和这道题设计巧妙的结论&#xff0c;相关内容请戳&#xff1a; 一道北大强基题背后的故事&#xff08;三&#xff09;——什…

stm32读取BH1750光照传感器

stm32读取BH1750光照传感器 一.序言二.BH1750指令三.IIC协议四.代码实例4.1 bh1750.c源文件4.2 bh1750.h头文件 一.序言 BH1750是用IIC协议进行数据传输的。有SCL,SDA&#xff0c;VCC,GND四根线。下图是原理图 二.BH1750指令 我们先看芯片手册的操作指令&#xff08;下图&a…

突破 Python 爬虫的瓶颈:WebKit 在线模拟技术与环境搭建

引言 在使用 Python 进行爬虫开发的时候,很多情况下我们需要利用一些浏览器内核来模拟浏览器行为。而目前最为常用的两种浏览器内核是基于 WebKit 和基于 Chromium 的内核。那么在 Windows 10 操作系统中,我们可以使用 Anaconda 作为 Python 的发行版,并基于此部署 WebKit 环…

Byte-of-python笔记代码2:module.py

#-*-coding:utf-8-*- ###import导入某模块 # import sys # # for i in sys.argv: # print(i) # print("\n\nThe Pythonpath",sys.path,"\n")# ##from math import sqrt,应该尽量避免使用from...import ... # from math import sqrt # print("16的…

2021-03-09

body{font: 12px/1.5 微软雅黑,宋体,arial,\5b8b\4f53; color:#333333;} html,body,dl,dt,dd,ul,ol,li,h1,h2,h3,h4,h5,h6,pre,form,fieldset,input, button,textarea,blockquote{ padding:0;margin:0; text-indent:0px;} html{zoom:expression(function(ele){ele.style.zoom …

Android网络连接判断与处理

1 http://www.cnblogs.com/qingblog/archive/2012/07/19/2598983.html 2 待续

《安富莱嵌入式周报》第315期:开源USB高速分析仪,8GHz示波器开发, 600行C编写RISC-V内核,英特尔推出用于开发人员等宽字体,便携物联网监测器

周报汇总地址&#xff1a;嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 视频版&#xff1a; https://www.bilibili.com/video/BV1gV4y117UD/ 《安富莱嵌入式周报》第315期&#xff1a;开源USB…

基于Hexo和Butterfly创建个人技术博客,(10) 使用Butterfly的Tags Plugin插件增强博客文章内容和视觉表现力

Butterfly官方网站&#xff0c;请 点击进入 说明&#xff1a; 前面已经提过Hexo自创了Tag Plugin内容标签&#xff0c;Butterflay主题在此基础上又扩展了一些。本文就详细讲解下这些标签带来哪些额外的功能和UI方面的强化&#xff1b; 本章目标&#xff1a; 掌握butterfly扩展…

CVE-2010-2883-PDF漏洞提权复现过程

第二步&#xff0c;打开Kali Linux渗透机使用命令msfconsole进入Metasploit渗透测试平台&#xff0c;使用模块adobe_cooltype_sing生成木马文件。 输入search adobe_cooltype_sing命令搜索Adobe渗透模块 与漏洞相关的模块有两个&#xff0c;编号为0的模块是使用本地的服务器挂…

力扣动态规划专题(二)01背包 416. 分割等和子集 1049.最后一块石头的重量II 494. 目标和 474. 一和零 步骤及C++实现

文章目录 01背包二维dp数组一维dp数组 滚动数组 416. 分割等和子集1049.最后一块石头的重量II494. 目标和474. 一和零 01背包 完全背包的物品数量是无限的&#xff0c;01背包的物品数量只有一个。 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]&#xf…

Pytest教程:Pytest命令行选项详解(很详细)

pytest 是一个流行的 Python 测试框架&#xff0c;它提供了许多命令行选项&#xff0c;可以帮助用户更好地控制测试执行过程。在使用 pytest 进行测试时&#xff0c;熟悉 pytest 的命令行选项非常重要&#xff0c;这将有助于减少错误和提高测试效率。本文将详细介绍 pytest 的命…

Python Crc32 介绍

文章目录 CRC32 介绍Python CRC32 本篇文章将介绍使用 Python 中的 binascii 或 zlib 库计算数据的 crc32。 CRC32 介绍 CRC32&#xff08;Cyclic Redundancy Check&#xff09;是一种循环冗余校验算法&#xff0c;常用于数据传输中的差错检测。它通过计算数据的校验值来检测数…

win10如何升级成win11系统

想要升级安装win11系统&#xff0c;电脑硬件配置需要满足一定的条件&#xff0c;而win10新版系统是可以免费升级到win11系统的。那么在满足配置条件的情况下&#xff0c;win10如何升级成win11系统呢&#xff1f;下面小编就给大家演示下win10升级成win11系统的方法。 一、升级前…

u盘启动盘安装win11系统

win11系统作为一个刚刚推出的新系统&#xff0c;在界面、性能、功能方面得到了很大的优化&#xff0c;因此有很多用户想要优先下载体验这款系统&#xff0c;那么win11系统怎么顺利安装呢?今天为大家分享使用u盘启动盘安装win11系统的操作教程。 准备工作&#xff1a; 将制作…

Windows 11 系统下载,正式版尚未发布

下载链接方式&#xff1a; 关注“郑州行疆户外”程序员自己的订阅号&#xff0c;回复“win11”&#xff0c;获取win11系统下载链接 一、发布 今年5月的Build大会&#xff0c;微软便正式明确新一代操作系统为Windows 11&#xff0c;厉兵秣马6年之后的今天&#xff0c;于6月24日…

win11系统怎么样 Windows11系统好用吗

Win11系统稳定吗?相信还有很多用户不太清楚&#xff0c;虽然Win11系统已经推出有一段时间&#xff0c;部分用户都在蹲反馈&#xff0c;所以下面小编来跟大家说说win11系统好不好用的详细介绍吧。更多Windows11系统教程可以参考小白装机网。 win11系统好不好用? 答&#xff…

Win11系统Python环境安装保姆级教程

1.访问网站www.python.org 2.点击Downloads--All releases进行下载 3.进入下载界面后进入Looking for a specific release按照自己的需求选择版本进行下载 4. 下载完成后选择双击运行即可 5. 安装第一步点击Customize installation选项&#xff08;选择第二个Customize install…
最新文章