P3819 松江1843路(洛谷月赛)
2024-08-27 19:59:58
P3819 松江1843路
题目描述
涞坊路是一条长L米的道路,道路上的坐标范围从0到L,路上有N座房子,第i座房子建在坐标为x[i]的地方,其中住了r[i]人。
松江1843路公交车要在这条路上建一个公交站,市政府希望让最多的人得到方便,因此希望所有的每一个的居民,从家到车站的距离的总和最短。
公交站应该建在哪里呢?
输入输出格式
输入格式:
第一行输入L、N。
接下来N行,每行两个整数x[i]和r[i]。
输出格式:
一个整数,最小的每个人从家到车站的距离的总和。
输入输出样例
输入样例#1:
100 3
20 3
50 2
70 1
输出样例#1:
110
输入样例#2:
100 2
0 1
100 10
输出样例#2:
100
输入样例#3:
10000000000 5
3282894320 391
4394338332 929
6932893249 181
7823822843 440
9322388365 623
输出样例#3:
5473201404068
说明
样例解释1
当建在坐标40的时候,所有人距离车站的距离总和为 |20−40|×3+|50−40|×2+|70−40|×1=110。
数据范围和约定
对于10%的数据,1≤N≤50,R[i]=1。
对于30%的数据,1≤N≤100,R[i]≤10,1≤L≤1000。
对于70%的数据,1≤N≤1000,R[i]≤100,1≤L≤10^6。
对于全部数据,1≤L≤10^10,1≤N≤10^5,0≤x[i]≤L,1≤r[i]≤1000
首先我们知道车站一定会建在所有人的中间,这样距离才可能最小,
这道题先把人数加起来,然后求中位数,相当于把n个人拆成n个点然后求中位数
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define LL long long
using namespace std; struct node{
LL pos,num;
bool operator < (const node &a) const
{
return pos < a.pos;
}
}t[];
LL l,n,sum,ans,s,p; int main()
{
scanf("%lld%lld",&l,&n);
for (LL i=; i<=n; ++i)
{
scanf("%lld%lld",&t[i].pos,&t[i].num);
sum += t[i].num;
}
sort(t+,t+n+);
sum = (sum+)/;
for (LL i=; i<=n; ++i)
{
s += t[i].num;
if (s>=sum)
{
p = t[i].pos;
break;
}
}
for (LL i=; i<=n; ++i)
ans += abs(t[i].pos-p)*t[i].num;
printf("%lld",ans);
return ;
}
最新文章
- UDP编程中client和server中使用recvfrom和sendto的区别
- makefile多目录的.c 格式.cpp混合编译
- ElasticSearch在Azure中的集群配置和Auto-Scale
- poj 1390 动态规划
- 锋利的Jquery解惑系列(一)------基本概念大锅炖
- iOS多线程总结(二)NSOperation
- 第四章 使用jQuery操作DOM
- Linux 64位下一键安装scipy等科学计算环境
- log4j2 标签解析
- let命令和块级作用域
- BZOJ3110[Zjoi2013]K大数查询——权值线段树套线段树
- JQuery 插件一般方法
- css的再深入4(更新中&#183;&#183;&#183;)
- vue 自定义组件directives
- 1098 Insertion or Heap Sort
- Java DB访问(一) JDBC
- import、export使用介绍
- C语言程序设计I—第六周教学
- JSP 表单处理
- 全局变量和局部变量(global关键字)