$Luogu2512/CH122\ AcWing122$糖果传递模拟

2021-02-08 08:18

阅读：350

标签：距离 tchar 图片 double href code char == mil

$Luogu$ $AcWing$

$Description$

有$n$个小朋友坐成一圈,每人有$a_i$个糖果.

每人只能给左右两人传递糖果.

每人每次传递一个糖果代价为$1$.

求使所有人获得均等糖果的最小代价.

$Sol$

感觉超级似曾相识,大概是寒假做过的题目.

求出平均数$x$,然后$a_i-=x$

设$i$小朋友给$i+1$小朋友$b_i$个糖果,特别地,$b_n$表示第$n$个小朋友给第$1$个小朋友的糖果.

$b_n+a_1-b_1=0\ \Leftrightarrow\ b_1=a_1+b_n=s_1+b_n$

$b_1+a_2-b_2=0\ \Leftrightarrow\ b_2=a_2+b_1=a_1+a_2+b_n=s_2+b_n$

就是$-b_n$到$s_1,s_2,....,s_n$的距离之和,要使之最小,$-b_n$就为$s_1,s_2,....,s_n$的中位数.

$over$

$Code$

#include#define il inline
#define Rg register
#define go(i,a,b) for(Rg int i=a;i#define yes(i,a,b) for(Rg int i=a;i>=b;i--)
#define ll long long
#define db double
using namespace std;
il int read()
{
    int x=0,y=1;char c=getchar();
    while(c‘0‘||c>‘9‘){if(c==‘-‘)y=-1;c=getchar();}
    while(c>=‘0‘&&c‘9‘){x=(x1)+(x3)+c-‘0‘;c=getchar();}
    return x*y;
}
const int N=1e6+1;
int n,a[N];
ll as,s[N];
int main()
{
    n=read();
    go(i,1,n)a[i]=read(),s[n]+=a[i];
    Rg int ave=s[n]/n,qwq;
    go(i,1,n)a[i]-=ave,s[i]=s[i-1]+a[i];
    sort(s+1,s+n+1);
    qwq=-s[n/2+1];//qwq=-b[n]
    go(i,1,n)as+=abs(s[i]+qwq);
    printf("%lld\n",as);
    return 0;
}

View Code

$Luogu2512/CH122\ AcWing122$糖果传递模拟

标签：距离 tchar 图片 double href code char == mil

原文地址：https://www.cnblogs.com/forward777/p/11283747.html

上一篇：windows下搭建vue开发环境实践

下一篇：python的os模块（ipython，文件，目录，权限，管理）

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：$Luogu2512/CH122\ AcWing122$糖果传递模拟
文章链接：http://soscw.com/index.php/essay/52564.html

亲，登录后才可以留言！

$Luogu2512/CH122\ AcWing122$糖果传递模拟

评论

热门文章

推荐文章

最新文章

置顶文章

$Luogu2512/CH122\ AcWing122$糖果传递 模拟

评论

热门文章

推荐文章

最新文章

置顶文章

$Luogu2512/CH122\ AcWing122$糖果传递模拟