100. 增减序列 (差分)

ゝ一世哀愁。 2022-08-31 02:26 73阅读 0赞

要求所有数都一样，那么只需要从2开始，差分数组为0就可以啦
贪心选择的过程就是，min(q, p) + abs(p-q) = max(p, q)
把正数和负数按最小的值互相兑掉，剩下abs(p-q) 拿头或者尾来兑换

最少也存在一中情况所以最后+1

  1. #include <iostream>
  2. using namespace std;
  3. const int maxn = 1e5+10;
  5. int a[maxn];
  6. long long p, q;
  8. int main()
  9. { 
  10.     int n;
  11.     scanf("%d", &n);
  12.     for (int i = 1; i <= n; i++)
  13.         scanf("%d", &a[i]);
  15.     for (int i = 2; i <= n; i++)
  16.     { 
  17.         long long c = a[i] - a[i-1];
  18.         if (c > 0) p += c;
  19.         else q -= c;
  20.     }
  21.     cout << max(p,q) << endl << abs(p-q) + 1;
  22.     return 0;
  23. }

发表评论

表情：
评论列表 （有 0 条评论，73人围观）

还没有评论，来说两句吧...

相关阅读

    相关 差分信号解释

     所谓差分方式传输，就是发送端在两条信号线上传输的幅值是相等的，相位是相反的电信号，如下图所示： ![20171222175545054][]        而对于接收端，

    小咪咪小咪咪/ 0 赞/ 351 阅读

    相关 差分

    概念 对于一个数组a\[n\]，有m次操作，都是对区间\[l,r\]加上k，完事后输出数组 在知道第一个数a\[1\]的情况下，如果我们知道后面的数与前一个数的差值p，

    我不是女神ヾ我不是女神ヾ/ 0 赞/ 441 阅读