洛谷-P3817-小A的糖果

小A的糖果 - 洛谷

解题思路：

1.由题意得，要求出最少吃的糖果数量。首先分析，如 果第一个糖果数没有超过x，并且第2个糖果数也没有 超过x，但是他们相加起来超过了x，那么应该吃哪个 盒子的呢，可以得到，因为第二个盒子关联着第三个 盒子，为了第三个盒子吃的更少，那么优先去吃第二 个盒子的，依次类推，这道题也就变成了每次都求局 部最优，让最后结果最优

2. 看数据范围，n不超过10^5，利用数组来模拟，a[i]最 大不超过int范围，但是可以想到，如果a[i]很大，并且 n也很大，所吃的糖果数量可能就超过Int，所以设置 累加器sum为long long 类型

3. 然后开始遍历，这里可以设置一个书签temp=2，如果 第一个盒子已经超过了x，那么第一个盒子肯定需要吃 a[1]-x个糖果，所以先对第一个盒子的糖果数进行预处 理，然后从temp位置，也就是第二个糖果盒开始判 断，if(a[temp]+a[temp-1]>x),那么 sum=sum+a[temp]+a[temp-1]-x；a[temp]=x-a[temp-1]; 此 时的糖果盒重新赋值 

4. 依次遍历，直到遍历完整个数组

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
    int n,x;
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    cin>>a[i];
 
    int temp=1;//设置书签从下标1开始 
    long long sum=0;//累加个数可能会超过int类型 
    while(1)
    {
        if(a[temp]+a[temp-1]>x)//如果当前项和前一项的和大于x 
        {
            sum=sum+a[temp]+a[temp-1]-x;//那么吃的糖果数量加上这两项和减去x的差 
            a[temp]=x-a[temp-1];//当前项重新赋值 
        }
 
        temp++;//书签移动 
        if(temp==n+1)//遍历完最后一项后结束循环 
        break;
    }
    cout<<sum;
    return 0;
}