题解 CF89A 【Robbery】

Nozebry · 2020-11-01 09:18:50 · 题解

Problems

有 n 个连续的房间，每个房间里放了 a_i个钻石。

现在有 k 分钟，每分钟能做 m 次操作。

可以的执行的操作有：

1.把一颗钻石从某一堆移到另一堆;
2.把一颗钻石从某一堆中装进口袋;
3.把一颗钻石从口袋取出放入某一堆钻石 。

要求：每分钟后，相邻两堆的钻石数量不变。

现在问你问 k 分钟后最多可以带走多少钻石？

Answer

这道题目我们先用分类讨论来解决：

No.1：当 n 为偶数时，不难发现，是拿不走钻石的。所以我们只需要考虑当 n 为奇数时的情况。

No.2：当 n 为奇数时，每偷一颗钻石的移动次数应该是 \frac{n}{2}+1 ，即把第奇数堆的一颗钻石向后移动一位，再从最后一堆取走一个。

以上分析可以看出，最大的偷取数量还会受到奇数堆钻石的最小数量的约束。

故最小数量应该是数组 a 中的最小值（且在奇数位上）与 \frac{m}{(\frac{n}{2}+1)}*k 两个数中的较小数。

Code

#include<bits/stdc++.h>
using namespace std;
long long a[100010],minn=555555555;
int main()
{
    long long n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if(i%2==1)minn=min(minn,a[i]);
    }
    if(n%2==0)
    {
        printf("0");
    }//当n位偶数时，无方案
    else
    {
        if(m<(n+1)/2)
        {
            printf("0");
        }
        else
        {
            long long ans1=m/((n+1)/2)*k,ans=min(minn,ans1);
            printf("%lld",ans);
        }
    }
}