Acwing-100-IncDec序列(差分)

2021-02-04 15:17

阅读：523

标签：下标 code typedef its 选择 names space abs print

链接:

https://www.acwing.com/problem/content/102/

题意:

给定一个长度为 n 的数列 a1,a2,…,an，每次可以选择一个区间 [l,r]，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

思路:

就是将查分数组除了第一位都置为0, 的操作步数,因为每次只能加1或减一.可以优先配对一正以偶负,再对剩余的值进行处理.

代码:

#include 
using namespace std;
typedef long long LL;

const int MAXN = 1e5+10;
int a[MAXN], Sub[MAXN];
int n;

int main()
{
    LL ne = 0, po = 0;
    scanf("%d", &n);
    for (int i = 1;i  0)
            po += Sub[i];
        else
            ne += abs(Sub[i]);
    }
    LL oth = abs(po-ne);
    printf("%lld\n%lld\n", max(ne, po), oth+1);

    return 0;
}

Acwing-100-IncDec序列(差分)

标签：下标 code typedef its 选择 names space abs print

原文地址：https://www.cnblogs.com/YDDDD/p/11462632.html

上一篇：Acwing-99-激光炸弹(二维前缀和)

下一篇：Windows查看端口使用状况(转)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Acwing-100-IncDec序列(差分)
文章链接：http://soscw.com/index.php/essay/50954.html

亲，登录后才可以留言！

Acwing-100-IncDec序列(差分)

链接:

题意:

思路:

代码:

评论

热门文章

推荐文章

最新文章

置顶文章