1 solutions

  • 1
    @ 2024-10-29 14:41:40

    我们先预处理,看一下每个数是需要增加多少,还是减少多少。

    然后看一下它前面的数,ai1a_{i-1}aia_i是否都是增加或减少。若相同考虑aia_i能否与ai1a_{i-1}合并,当然此时两个数增加减少的数可能不同,那么该考虑如何合并

    另一种思路差分 每次操作可以选择一次性操作一串,或者只操作一个

    遇到这种区间操作想到差分,对于差分后的数组,操作选择一个区间 l 和 r ,s[l] + 1, s[r + 1] - 1,想办法把差分数组变为0

    同时影响是相邻间传递的

    #include<bits/stdc++.h>
    #define LL long long
    using namespace std;
    
    int n;
    int a[100100];
    
    int main ()
    {
    	cin >> n;
    	for(int i = 1;i <= n;++ i)
    	{
    		cin >> a[i];
    	}
    	for(int i = 1;i <= n;++ i)
    	{
    		int temp;
    		cin >> temp;
    		a[i] -= temp;
    		
    	}
    	for(int i = n;i > 0;i --)
    	{
    		a[i] -= a[i - 1];
    	}
    	int j = 0;
    	int k = 0;
    	for(int i = 1;i <= n;++ i)
    	{
    		a[i] >= 0 ? j += a[i] : k -= a[i];
    	}
    	cout << max(j,k);
    	return 0;
    }
    

    Information

    ID
    6996
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    6
    Tags
    (None)
    # Submissions
    39
    Accepted
    12
    Uploaded By