当前位置:网站首页>Candy delivery (Mathematics)
Candy delivery (Mathematics)
2022-07-06 16:08:00 【AC__ dream】
This problem is essentially a mathematical problem , Presuppose xi In the best case i A child gave it to No i-1 The number of sweets for a child (xi A negative number means the i-1 A child gave the first i A child candy ), A special case : When i by 1 when , Default i-1=n, That is to say x1 It means the first one 1 A child gave it to No n The number of sweets for a child . Then our The result is all xi The sum of the absolute values of ( The number of candy delivered is the final price ), The title has given the number of sweets each child had at the beginning ai, Let the number of sweets each child finally gets be mid, So the first i The final number of sweets for children mid Depends on the number of sweets you have at the beginning ai And he gave No i-1 The number of sweets for a child xi And the first i+1 A child gave him the number of sweets xi+1, That is to say mid=ai-xi+x(i+1), Simplify to x(i+1)-xi=mid-ai, From this formula, we can get
(1) x2-x1=mid-a1
(2) x3-x2=mid-a2
……
(n-1) xn-x(n-1)=mid-a(n-1)
Combining the above formulas, we get
(1)+(2) have to x3-x1=2*mid-(a2+a1)
(1)+(2)+(3) have to x4-x1=3*mid-(a3+a2+a1)
……
(1)+(2)+……+(n-1) have to xn-x1=(n-1)*mid-(a(n-1)+a(n-2)+……+a1)
Move the terms of the merged formula to get :
x2=x1-(a1-mid)
x3=x1-((a2+a1)-2*mid)
x4=x1-((a3+a2+a1)-3*mid)
……
xn=x1-((a(n-1)+……+a2+a1)-(n-1)*mid)
Again because x1=x1-0
Our final result is xi The sum of the absolute values of , It's easy to think of the distance formula when you see the formula after the term shift above , So our result is One point to 0,(a1-mid),((a2+a1)-2*mid),……,((a(n-1)+……+a2+a1)-(n-1)*mid) The minimum value of the sum of the distances of these points , This can be transformed into the problem of warehouse location , Directly take a median for calculation , Here is the code :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1000003;
long long a[N],s[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
}
long long mid=s[n]/n;
for(int i=1;i<=n;i++)
s[i]-=i*mid;
sort(s,s+n);
long long ans=0;
for(int i=0;i<n;i++)
ans+=abs(s[i]-s[n/2]);
printf("%lld",ans);
return 0;
}
边栏推荐
- 1005. Maximized array sum after K negations
- 7-1 understand everything (20 points)
- 渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
- 渗透测试 ( 3 ) --- Metasploit Framework ( MSF )
- C language must memorize code Encyclopedia
- 1323. Maximum number of 6 and 9
- Opencv learning log 29 -- gamma correction
- Determine the Photo Position
- 双向链表—全部操作
- Research Report of cylindrical grinder industry - market status analysis and development prospect forecast
猜你喜欢
树莓派4B安装opencv3.4.0
1013. Divide the array into three parts equal to and
X-Forwarded-For详解、如何获取到客户端IP
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
B - Code Party (girls' competition)
Frida hook so layer, protobuf data analysis
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
C language is the watershed between low-level and high-level
1903. Maximum odd number in string
Nodejs+vue网上鲜花店销售信息系统express+mysql
随机推荐
Research Report of exterior wall insulation system (ewis) industry - market status analysis and development prospect prediction
Research Report on market supply and demand and strategy of China's earth drilling industry
【练习-7】(Uva 10976)Fractions Again?!(分数拆分)
1010 things that college students majoring in it must do before graduation
【练习-2】(Uva 712) S-Trees (S树)
Ball Dropping
[exercise-7] (UVA 10976) fractions again?! (fraction split)
[exercise-6] (PTA) divide and conquer
【高老师软件需求分析】20级云班课习题答案合集
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
C language must memorize code Encyclopedia
Luogu P1102 A-B number pair (dichotomy, map, double pointer)
Shell脚本编程
对iptables进行常规操作
Flink 使用之 CEP
渗透测试 ( 3 ) --- Metasploit Framework ( MSF )
The concept of C language array
STM32 learning record: LED light flashes (register version)
【高老师UML软件建模基础】20级云班课习题答案合集
Shell Scripting