洛谷七月月赛A题(3817) 小A的糖果题解

题目

小A有N个糖果盒，第i个盒中有a[i]颗糖果。

小A每次可以从其中一盒糖果中吃掉一颗，他想知道，要让任意两个相邻的盒子中加起来都只有x颗或以下的糖果，至少得吃掉几颗糖。

题解

对于每两个相邻的糖果盒，如果我们假设左边的糖果盒有$a$颗糖果，右边的糖果盒有$b$颗糖果，并且$a+b>x$，那么就将$b$减去超过$x$的部分$a+b-x$颗，若此时$b<0$，则$a$糖果盒减去$-b$颗。这样吃掉的糖可以最少。

代码

#include<cstdio>
const int MAXN=100000+5;
int candy[MAXN];long long ans;
int main()
{
    int n,x;
    scanf("%d %d",&n,&x);
    for(int i=1;i<=n;i++)
        scanf("%d",&candy[i]);
    for(int i=2;i<=n;i++)
        if(candy[i-1]+candy[i]>x)
        {
            ans+=-x+candy[i-1]+candy[i];
            candy[i]-=-x+candy[i-1]+candy[i];
            if(candy[i]<0) 
            {
                candy[i-1]=-candy[i];
                candy[i]=0;
            }
        }
    printf("%lld",ans);
    return 0;
}

洛谷七月月赛B题(3818) 小A和uim之大逃离 II 90分题解

题目瞬间，地面上出现了一个H行W列的巨幅矩阵，矩阵的每个格子上要么是空地‘.’或者障碍’#’。他们起点在(1,1)，要逃往(H,W)的出口。他们可以一次向上下左右移动一格，这个算一步操作。不过他们还保留着上次冒险时收集的魔液，一口气喝掉后可以瞬移到相对自己位置的(D,R)向量；也就是说，原来的位置 …

Vijos 1454 牛的RP 题解

题目天苍苍，野茫茫，JSZX的菜鸟们来到OI牧场旅游，看到了好多好多的牛。OI牧场所有的牛都觉得自己的Rp最高（简称RP牛），为此他们常争论不休。于是，他们让JSZX的菜菜们用最最朴素的方法找出这只RP牛。经过讨论，最菜的mmk想出了最朴素的方法：我们要以cows的名字为线索，来找出RP牛。首先，得 …