ACM模版

描述

题解

一开始考虑从头至尾遍历，但是发现对于第二种移动方式往后移动时，需要额外标记一下，和没有移动过的区分开来，比较麻烦，所以考虑从尾至头遍历。

从尾往前遍历时，我们需要时刻关注 sum+=y[i]−x[i] s u m + = y [ i ] − x [ i ] 的值，当它大于零时，说明不够，需要通过第二种方式来获取，我们可以将第二种方式拆分为两步，第一步是和第一种方式一样，第二步是从位置 (1,1) ( 1 , 1 ) 往后移动，第一步和第一种方式合并考虑，所以这里我们只用考虑第二步的消耗，也就是从位置 (1,1) ( 1 , 1 ) 移动到 (1,i) ( 1 , i ) ；当它小于零时，说明此时多余了，需要往前移动，那么多出 −sum − s u m 个棋子，我就向前移动一步就需要 −sum − s u m 的代价。

这样遍历结束后，可以保证所有多余的都移动到 (1,1) ( 1 , 1 ) ，然后通过第二步移动到了该放的位置，不过我们的思路是率先透支了这个额度，将他放到了该放的位置，因为我们遍历结束时，可以保证所有多余的会移动到位置 (1,1) ( 1 , 1 ) 来弥补上这个透支。

这里需要强调 sum +=y[i]−x[i] s u m   + = y [ i ] − x [ i ] ，因为当我们考虑 (1,i) ( 1 , i ) 时，该位置的棋子个数并不一定是 x[i] x [ i ] ，而是 x[i]−sum x [ i ] − s u m ，所以这里我们使用 += + = 来操作。

代码

#include <iostream>

using namespace std;

const int MAXN = 1e5 + 10;

int n;
int x[MAXN], y[MAXN];

int main(int argc, const char * argv[])
{
    while (cin >> n)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", x + i);
        }
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", y + j);
        }

        long long ans = 0, sum = 0;
        for (int i = n; i >= 2; i--)
        {
            sum += y[i] - x[i];
            if (sum > 0)
            {
                ans += sum * (i - 1);
                sum = 0;
            }
            else
            {
                ans -= sum;
            }
        }

        cout << ans << '\n';
    }

    return 0;
}