#include<bits/stdc++.h>
using namespace std;
long long v[10005];
int main () {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> v[i];
//sort(v + 1, v+n + 1);// 排序 1~n的位置
// 快速排序，归并排序。
long long t = (n + 1) / 2;
nth_element(v + 1, v + t, v + 1 + n);
long long sum = 0, k = v[t];
// 第1个参数表示起始位置，第3个参数表示终止位置，第2个参数，表示这个参数的位置就是排序好的数组
//该有的位置。但它不是排序
// 1 3 9 4 2
// sort(a, a + 1, a + n);//a是从0开始的数组
// 1 2 9 3 4
// string a = "9123456"; vector<int> b{1,5,2,3};
// sort(a.begin(), a.end());
// sort(b.begin(), b.end());
for (int i = 1; i <= n;i++) sum += abs(k - v[i]);
cout << sum << endl;
return 0;
}
使用long long ，并且很容易想到，中位数是距离最小的位置。可以推导出来。比如，如果枚举到某点，靠左，则右边的点Ri更多，那么，这个点越向左移动，总距离增加 Li - Ri，所以点只能向右移动。
同理,点靠右则只能向左移动。
所以，该点只能是中位数。
如何求中位数？sort()排序，那么中间那个数就是中位数。复杂度就是nlogn
或者使用algorithm中提供的另一个库函数。nth_element(),第1，3，参数标记其实和终止的位置，可以是迭代器。中间第2个参数k也是迭代器，那么。该函数执行完毕之后，也会令k位置的数，一定是排序后的数。也就是说，前面k - 1个数都小于等于a[k]，后面n - k个数都大于等于a[k]，但是这些数没有排序。具体用法在cppreference中。
#include<bits/stdc++.h>
using namespace std;
long long v[10005];
int main () {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> v[i];
//sort(v + 1, v+n + 1);// 排序 1~n的位置
// 快速排序，归并排序。
long long t = (n + 1) / 2;
nth_element(v + 1, v + t, v + 1 + n);
long long sum = 0, k = v[t];
// 第1个参数表示起始位置，第3个参数表示终止位置，第2个参数，表示这个参数的位置就是排序好的数组
//该有的位置。但它不是排序
// 1 3 9 4 2
// sort(a, a + 1, a + n);//a是从0开始的数组
// 1 2 9 3 4
// string a = "9123456"; vector<int> b{1,5,2,3};
// sort(a.begin(), a.end());
// sort(b.begin(), b.end());
for (int i = 1; i <= n;i++) sum += abs(k - v[i]);
cout << sum << endl;
return 0;
}
这里要用到一个结论，如果一个数本身是k的倍数，那么这个数所有位上的和，也是k的倍数。具体推导可以在知乎看到。
大概如下推导：比如abcd是3 的倍数。
一个整数如abcd
可以写成1000×a+100×b+10×c+d
＝999×a+99×b+9×c+a+b+c+d
这道题如果使用vector<int> G[N]这样的数据，会很简单，G[N]这个vector可以储存N这个节点的所有子节点。
本题解使用链式前向星去理解储存树。
不懂的去bilibili看教程
//
// Created by YMXD on 2021/10/20.
//
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+50;
struct Edge{
int to,next;
};
int n, tot = 0, ans, head[maxn], cnt[maxn];
Edge edges[maxn<<1];
void add(int u,int v){
edges[tot].to=v;
edges[tot].next=head[u];//先初始化一个树，再把这个树放到链表前面
head[u]=tot++;
}
void dfs(int u,int fa,int d){
cnt[u] = 1;
for(int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
if(v!=fa){
dfs(v,u,d+1);
cnt[u]+=cnt[v];
}
}
ans += cnt[u];
return;
}
int main(){
memset(head,-1,sizeof(head));
cin >> n;
for(int i=0;i<n-1;++i){
int u,v;
cin >> u >> v;
add(u,v);// u 和v相连
add(v,u);// v和u相连
}
dfs(1,0,1);// 1这个节点， 没有父节点所以填0， size是1.
cout << ans;
return 0;
}
文章浏览阅读296次。这里写目录标题事务的ACID特性数据库的事务是什么？隔离性（Isolation）概念说明脏读可重复读不可重复读：一个事务A，不同时刻读同一数据可能不一样幻读：事务A,B同时Insert,B先提交，A没有察觉InnoDB支持的事务隔离级别MySQL 中执行事务1.读未提交:不加锁2.读提交：解决update/inerst引入的脏读,无法做到可重复读3.可重复读：解决update引入的不可重复读，不能解决Insert引入的幻读总结：MySQL 中是如何实现事务隔离的：可重复读可重复读——多版本——针对一条事务可_唯一键索引冲突是inster时产生的还是commit的时候
文章浏览阅读2.8k次。qt介绍 qt是一套完整到跨平台解决方案古老但高效。主要是用c++语言 qt 有自己的sdk以及编辑器，就像vs一样。到官网下载最新到qt版本。安装打包一篇比较解决问题的打包文章 还有这个 1，将依赖库添加到导出到releaseapp中。也就是说releaseapp默认没有依赖库。 命令： ./Qt安装目录/clang_64/bin/macdeployqt re..._qt for mac生成的.app应用怎么变成非.app应用
文章浏览阅读76次。没有人会想到，地球的命运，会因为十二个小时而改变。当氪星球面临毁灭，他们把这个孩子装入太空舱，送向宇宙。这小小的太空舱在宇宙中漂流，穿越一个又一个星云，那在宇宙中飘动了万年的光流风暴和物质云把这个孩子他推向他的终点，太阳系——地球——北美洲——美国——堪萨斯州——莫维尔小镇。如果一切都没有偏差，如果每一颗恒星的引力都恰到好处，他会变成美国英雄、传奇的超人。但是，宇宙间一颗计算外的只有三万之分一立方..._中国式青春今何在下载
文章浏览阅读1.5k次，点赞3次，收藏16次。要求：将滑块与编辑框、进度条相连接。调整滑块位置同时显示滑块当前对应数值，达到设定要求时改变进度条的进度。一、界面设计滑块是slider control，进度条是progress control对于三个滑块，修改属性：对于三个示例编辑框，修改属性：二、添加变量三、初始化滑块和进度条在Dlg.cpp中找到初始化函数BOOL COOPEx3Dlg::OnI..._setticfreq
文章浏览阅读202次。packagecode;//importjava.awt.*;//importjava.awt.Canvas;//importjava.awt.event.*;//importjavax.swing.*;importjava.util.Random;importjavax.microedition.lcdui.*;//写界面所需要的包/***//***俄罗斯方块*高雷*2007年1..._240×320java游戏
文章浏览阅读779次，点赞14次，收藏19次。然后，实现系统的数据管理和服务功能，包括用户的注册与登录、电影的分类与展示、电影信息的查询与推荐、座位的选择与预订、在线支付与电子票生成等。此外，随着在线视频平台的兴起，越来越多的人选择在线观看电影，这对传统电影院产生了巨大的冲击。研究意义： 开发在线电影院售票平台对于提升用户的观影体验、优化电影院的运营效率、促进电影产业的发展具有重要的意义。该系统旨在通过技术手段解决传统电影院售票中的问题，提供一个集成化的电影信息展示、座位选择、在线支付和用户评价平台，同时也为电影院和电影制作方提供有效的工具。
文章浏览阅读239次。开发四年只会写业务代码，分布式高并发都不会还做程序员？ >>> Lucene PMC 宣布推出 Ap..._lucene 8.0.0
文章浏览阅读87次。原标题：【趣事】Java程序员最年轻，C++程序员最年老说起我们对编程世界现有的刻板印象，你一定听说过类似于没有人喜欢用Java编码或者使用C ++都是老人家，等等这样的话。为了分析这些刻板印象背后的真相，Trestle Technology的数据工程师写了一个工具。不知道你有没有听说过微软的Project Oxford，它的Face API可以检测图像中的人脸，并检测这个人是否在笑，他/她的性别..._胡须程序
文章浏览阅读1.2w次。内存从某种意义上来说对于电脑的运行会产生着基础性的影响，所以我们需要经常的检测一下我们电脑的稳定性，那么下载一款内存条监测工具对我们来说就非常的有必要了，现在的内存条检测工具有很多，那么我们应该如何选择一款合适的内存条监测工具呢，接下来就为大家介绍一下。【鲁大师】这是一款综合的电脑检测软件，不仅仅可以对我们电脑内存当中的内存进行检测，还可以对我们的电脑系统的方方面面都进行监测，比如说我们的内存占比..._怎么测试内存稳定性
文章浏览阅读7.8k次。自定义一个下拉列表框，当这个功能有效时，点击可弹出下拉框，选中某个选项后，在左边功能名称下面显示选项值，右边的箭头替换成自定义图标，例如手法功能；当功能无效时，置灰，如力度功能；具体示例如下：代码如下：index.hml<!--手法无效时--><div class="fun-grid-item" if="{{manualInvalid}}"> <div class="grid-item-parent-ver._harmonyos 下拉列表
文章浏览阅读1k次。第44集 图片与图形处理198、 Shape对象的类型和属性该对象代表工作表或图形工作表上的所有图形,它是sheets和chart的子对象（属性）。Sheet1.ShapesSub t2()On Error Resume NextDim ms As Shapek = 1For Each ms In Sheet1.Shapesk = k + 1Cells(k, 1) = ms.Na..._msofalse
文章浏览阅读1.2k次。公司个人年终工作总结1 20__年即将过去，在公司领导的悉心关怀下和同事们的帮助指导下，结合我自身的努力，在工作、学习等各方面都取得了长足的进步，尤其是在保险理赔专业知识和技能培养方面的成熟，使我成为一名合格的车险查勘定损员。随着工作岗位的调整，我已经成长为为一名能够独立工作、业务熟练的前台工作人员。现将一年来的工作情况向公司领导总结汇报如下： 一、加强理论学习，注重个人素质提高 加强自身业务学习，争做理赔标兵。在日常的工作学习中，我坚持学习更多的保险知识和业务技能，在老同志的“传帮带”下，不断加强个_csdn 公司 年终终结