hihocoder#1499:ABoxofCoins贪心

+----+----+----+----+----+----+
| A1 | A2 | A3 | A4 | .. | AN |
+----+----+----+----+----+----+
| B1 | B2 | B3 | B4 | .. | BN |
+----+----+----+----+----+----+

2
3 4
6 7

4

.

题意 给出两行 A B 格子 里面放有一定数量的硬币

要求使得最后每个格子的硬币数量一样（输入保证合法）

移动每次只允许硬币在上下左右相邻的格子之间移动

求最少步数

贪心：

从最左边考虑，如果上下之间有一个有盈余，必定是相互补充最优。

其次 如果上下两个都有富余，则都往右边输送

再者 如果上下之间都缺乏，则都向左借

模拟即可  .

#include 
using namespace std;
typedef long long ll;

ll n,q;
ll A[2][100050];
int main()
{
     int n;
     cin>>n;
     ll tol=0;
     for(int i=1;i<=n;i++)
     {
         scanf("%lld%lld",&A[0][i],&A[1][i]);
        tol+=A[0][i]+A[1][i];
     }
     tol/=2*n;
     ll sum=0;
     ll nn=n;
     n=tol;
     for(int i=1;i<=nn;i++)
     {
         if (A[0][i]>n)        //superfluous
         {
             ll res=A[0][i]-n;
             if (A[1][i]0)
             {
                 ll tmp=min(res,(n-A[1][i]));
                 A[0][i]-=tmp;
                 sum+=tmp;
                 res-=tmp;
                 A[1][i]+=tmp;
             }
             if (res>0)
             {
                 A[0][i+1]+=res;
                 sum+=res;
                 A[0][i]=n;
             }
         }
         if (A[1][i]>n)
         {
             ll res=A[1][i]-n;
             if (A[0][i]0)
             {
                 ll tmp=min(res,(n-A[0][i]));
                 A[1][i]-=tmp;
                 sum+=tmp;
                 res-=tmp;
                 A[0][i]+=tmp;

             }
              if (res>0)
             {
                 A[1][i+1]+=res;
                 sum+=res;
                 A[1][i]=n;
             }
         }
         if (A[0][i]0)
             {
                 A[0][i+1]-=need;
                 sum+=need;
                 A[0][i]=n;
             }
         }
         if (A[1][i]0)
             {
                 A[1][i+1]-=need;
                 sum+=need;
                 A[1][i]=n;
             }
         }

     }
     printf("%lld\n",sum);

    return 0;
}