vijos p1882 智力题

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意:

清晨, Alice与Bob在石阶上玩砖块.
他们每人都有属于自己的一堆砖块.
每人的砖块都由N列组成且N是奇数.
Alice的第i列砖块有m[i]个.
而Bob的第i列砖块有s[i]个.

他们想建造城堡, 两座一样的城堡.
每一座城堡都是从正中间一列开始:
1)若往左侧看去,数量逐次增加,每一列都比右侧的一列多出恰一块砖.
2)若往右侧看去,数量逐次增加,每一列都比左侧的一列多出恰一块砖.

那么,最左侧与最右侧的高度当然是一样的呵.

每一次.
他们可以扔掉一块砖头,以减少某一列的砖头数量.这算是一次操作.
他们可以再找一块砖头,以增加某一列的砖头数量.这又算是一次操作.
但是.
不能从一列去除一块砖头,再放置到别的列中.
被扔掉的砖头,永远也不能再被使用.

最少,最少,需要多少次操作?

链接：点我

从中间开始减去应该少的高度，最后就是求使所有数字都相同的步骤，而那个相同的数字就是中位数

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 #include<map>

 using namespace std;

 #define MOD 1000000007

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 #define cl(a) memset(a,0,sizeof(a))

 #define ts printf("*****\n");

 const int MAXN=;

 int n,m,tt;

 long long a[MAXN],b[MAXN],o[MAXN*];

 int main()

 {

     int i,j,k;

     while(scanf("%d",&n)!=EOF)

     {

         for(i=;i<=n;i++)   scanf("%I64d",a+i);

         for(i=;i<=n;i++)   scanf("%I64d",b+i);

         int mid=(+n)/;

         for(i=;i<=mid;i++)

         {

             a[mid-i]-=i;

             a[mid+i]-=i;

             b[mid-i]-=i;

             b[mid+i]-=i;

         }

         for(i=;i<=n;i++)

         {

             o[i]=a[i];

             o[i+n]=b[i];

         }

         sort(o+,o+*n+);

         long long q=o[n];

         long long ans=;

         for(i=;i<=*n;i++)

         {

             ans+=fabs(q-o[i]);

         }

         printf("%I64d\n",ans);

     }

 }