2022/7/14 cf训练(思维+构造+差分)

C. Helping the Nature 一道构造题。 难度：1700 题意：经过题目给定三种操作，1~i都减去1、i ~n都减去1、1 ~n都加上1，使得数组中所有值都为0，问最少需要多少次操作。 思路：乍一看觉得不难，但有几个点需要相通。 1.0 0 8 0 0需要24次操作，才能全部归0 2.若原始值中有负数，需要将其转化为非负数。 3.以0作为间隔来考虑最小次数。

只能想到这里，后面怎么处理就想不通了，看了dalao题解，几点提示： 1.看到对一段区间的操作，应马上想到一个工具----差分。创建一个差分数组b[N] 2.1~i都减去1---->b[1]-=1,b[i+1]+=1 3.i ~n都减去1—>b[i]-=1 4.1 ~n都加上1—>b[1]+=1

接下来分为两个步骤： 1.如果数组a中的值要全部相等，则b[1]=a[1]，b[2~n]全部为0。操作2，3可对b[2 ~n]操作。 2.a数组中值如果全部为0，则在(1)的基础上b[1]必须为0。

代码： 顺利ac了，需要思考的东西很多，wa了一发，老问题没开longlong

#include
#define int long long
using namespace std;
const int N=1e6+6;
int n,a[N],b[N];
signed main()
{
    int t;cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i>a[i];
        b[1]=a[1];
        for(int i=2;is;
        int g=s.length();
        for(int i=0;i