title: 2019牛客国庆集训派对 E-Partial Sum （绝对值的特殊性）
categories: 2019牛客国庆集训派对
top: false
tags:

  • acm
  • 绝对值的特殊性
  • 思维

题目大意

题目链接
给定长为n的数组， 找到m组(L, R)， 使得|sum（L,R）| - C的和最大， 其中C为常数（输入中给出）， 每个(L, R)只出现一次。

思路

求区间前缀和， 因为绝对值的特性， |sumi - sumj = sumj - sumi| 所以前后减的顺序没关系， 他也没
要求具体是那m组， 所以sort后 最大减最小就可。

AC代码

#include <bits/stdc++.h>

using namespace std;

#define eps 1e-8

typedef long long ll;

typedef pair<ll, int> P;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int mod = int(1e9) + 7;
const int N = int(1e5) + 10;

int sum[N];

int main() {
    std::ios::sync_with_stdio(0);
    int n, m, c, x;
    while(cin >> n >> m >> c){
        sum[0] = 0;
        for (int i = 1; i <= n; i++){
            cin >> x;
            sum[i] = sum[i - 1] + x;
        }
        sort(sum, sum + n + 1);
        int l = 0, r = n;
        ll ans = 0;
        while(m--){
            int temp = sum[r] - sum[l] - c;
            if (temp <= 0)
                break;
            l++, r--;
            ans += ll(temp);
        }
        cout << ans << "\n";
    }

    return 0;
}




恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan