当前位置：首页 > news >正文

打卡信奥刷题（3065）用C++实现信奥题 P6874 [COCI 2013/2014 #6] KOCKICE

news 2026/6/16 15:48:04

P6874 [COCI 2013/2014 #6] KOCKICE

题目背景

堆积木！

题目描述

Mirko 和 Slavko 在玩积木。他们俩都有自己的一堆砖头。一共有N NN列砖头（其中N NN为奇数）。

Mirko 桩的第i ii列中有m i m_imi块砖，而 Slavko 每列有s i s_isi个。

他们决定创建两堆一样的砖头，这几堆的高度首先是严格下降，然后是严格上升（参见下方右图），相邻列的高度恰好相差1 11（见图）。最低的列的左右两侧的砖头数量必须相同。

允许两种操作：

从某一列的顶部移除一块砖。
在某一列的顶部加上一块砖。

问在满足上述要求的情况下，最少要几次操作？

输入格式

输入的第一行包含一个奇数N NN，即两个人砖头的堆数。

输入的第二行包含N NN个整数m i m_imi，即 Mirko 堆中的列高。

输入的第三行包含N NN个整数s i s_isi，即 Slavko 堆中的列高。

输出格式

输出所需的最少操作次数。

输入输出样例 #1

输入 #1

3 1 2 3 3 2 2

输出 #1

输入输出样例 #2

输入 #2

5 2 3 0 1 4 3 3 2 3 1

输出 #2

说明/提示

样例 1 解释

Mirko 在其桩的第一列的顶部放置了两块砖，而 Slavko 在他桩的第三列的顶部放置了一块砖。

【数据规模与约定】

对于40 % 40\%40%的数据，满足1 ≤ N ≤ 1000 1\le N\le 10001≤N≤1000，0 ≤ m i , s i ≤ 1000 0\le m_i,s_i\le 10000≤mi,si≤1000。
对于100 % 100\%100%的数据，满足1 ≤ N ≤ 3 × 10 5 1\le N\le 3\times 10^51≤N≤3×105，0 ≤ m i , s i ≤ 10 12 0\le m_i,s_i\le 10^{12}0≤mi,si≤1012。

【说明】

题目译自 COCI2013-2014 CONTEST #6T3 KOCKICE。

C++实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;ll l,r,a[300009],b[300009],n;llabs_(ll x){return(x>=0?x:-x);}llchk(ll t){ll ans=0;for(ll i=0;i<n;i++)ans+=abs_(t-a[i]+abs_(n/2-i));for(ll i=0;i<n;i++)ans+=abs_(t-b[i]+abs_(n/2-i));returnans;}voidprint(ll t){printf("%lld\n",chk(t));return;}intmain(){scanf("%lld",&n);for(ll i=0;i<n;i++)scanf("%lld",a+i);for(ll i=0;i<n;i++)scanf("%lld",b+i);l=0ll;r=1000000000001ll;while(l<r){//二分ll mid=(l+r)/2;if(chk(mid+1)>chk(mid))r=mid;elsel=mid+1;}print(l);return0;}