hiho一下第257周《A Box of Coins》题目分析

0
0

《A Box of Coins》题目分析

本题是一道贪心的题目。

我们不妨先思考一下只有一排的情况。假设只有只有一排是A1, A2, .... AN，硬币只能左右相邻移动，并且平均值是ave。

这时考虑A1，因为A1只能和A2交换硬币。所以如果A1 >= ave，那么一定需要将(A1 - ave)个硬币从A1移动到A2；反之，如果A1 <= ave，那么一定需要将(ave - A1)个硬币从A2移动到A1。

注意上述移动是一定会发生的，不然A1不可能变成ave。而移动之后A1' = ave，A2' = A2 + (A1 - ave)。

这时A1'不会再发生变化，A2'也只能跟A3交换硬币，于是我们可以重复上述的贪心策略。直到所有格子里的硬币都是ave，这时总共移动的硬币数就是答案。

当扩展的2排的时候。我们仍然可以从左向右考虑。

首先考虑A1和B1。它们除了两者之间能交换硬币之外，只能同A2和B2交换。

与1排时的分析类似，如果A1 >= ave且B1 >= ave，那么一定是将(A1 - ave)个个硬币从A1移动到A2并且将(B1 - ave)个个硬币从B1移动到B2。 先A1与B1之间移动若干硬币，再将多余的硬币移动到A2B2的方案一定不会是最优的。

同理如果A1 <= ave且B1 <= ave，那么一定是将(ave - A1)个个硬币从A2移动到A1并且将(ave - B1)个个硬币从B2移动到B1。 先A1与B1之间移动若干硬币，再从A2B2补充硬币的方案一定不会是最优的。

最后，如果A1,B1其中一个大于ave一个小于ave，不妨设A1 > ave且B1 < ave；那么应当A1先移动 min(A1 - ave, ave - B1) 枚硬币至B1。然后如果A1有盈余则移动到A2，如果B1有不足则从B2补充。

  • 当A1 <= ave 时，将（ave-A1）个硬币从A2移动到A1，有可能A2的个数小于(ave-A1)个。

  • 注意输入是按列输入的。。。

  • 添加评论
  • ✖reply

1 answer(s)

0

一直WA，自己测试没找到问题，谁能帮忙看看么？

int main() {

int n;

scanf("%d", &n);

long long int A[array_size], B[array_size];
long long int sum = 0;

for(int i=0; i<n; i++) {
    scanf("%lld", &A[i]);
    sum += A[i];
}
for(int i=0; i<n; i++) {
    scanf("%lld", &B[i]);
    sum += B[i];
}
int ave = sum/(2*n);

long long int ans = 0;

for(int i=0; i<n; i++) {

    if( A[i] >= ave && B[i] >= ave ) {
        int cur = A[i]-ave;
        ans += cur;
        A[i+1] += cur;

        cur = B[i]-ave;
        ans += cur;
        B[i+1] += cur;
    }
    else if(A[i]<=ave && B[i]<=ave) {
        int cur = ave-A[i];
        ans += cur;
        A[i+1] -= cur;

        cur = ave-B[i];
        ans += cur;
        B[i+1] -= cur;
    }
    else if(A[i] > ave && B[i] < ave) {
        ans += min(A[i]-ave, ave-B[i]);
        if( (A[i]-ave) > (ave-B[i]) ) {
            int cur = A[i]-ave-ave+B[i];
            ans += cur;
            printf("A: %d\n", ans);
            A[i+1] += cur;
        }
        else if( (A[i]-ave) < (ave-B[i]) ){
            int cur = ave+ave-A[i]-B[i];
            ans += cur;
            B[i+1] -= cur;
        }
    }
    else if(A[i] < ave && B[i] > ave) {
        ans += min(ave-A[i], B[i]-ave);
        if( (ave-A[i]) > (B[i]-ave) ) {
            int cur = ave+ave-A[i]-B[i];
            ans += cur;
            A[i+1] -= cur;
        }
        else if( (ave-A[i]) < (B[i]-ave) ) {
            int cur = A[i]+B[i]-ave-ave;
            ans += cur;
            B[i+1] += cur;
        }
    }
}
printf("%d\n", ans);
return 0;

}

write answer 切换为英文 切换为中文

转发分享

▲