来自算法基础课

贪心的分析方法：

• 猜
• 证明

区间问题

1. 区间选点

struct Range{
    int l, r;

    bool operator< (const Range& W)const{
        return this->r < W.r;
    }
}ranges[N];

int n;

int main(){
    input();
    sort(ranges, ranges + n);
    int cnt = 0, end = -0x3f3f3f3f;
    for(int i = 0; i < n; i ++)
        if(end < ranges[i].l){
            cnt ++;
            end = ranges[i].r;
        }
    print(res);
    return 0;
}

2. 最大不相交区间数量

struct Range{
    int l, r;

    bool operator< (const Range& W)const{
        return this->r < W.r;
    }
}ranges[N];

int n;

int main(){
    input();
    sort(ranges, ranges + n);
    int cnt = 0, end = -0x3f3f3f3f;
    for(int i = 0; i < n; i ++)
        if(end < ranges[i].l){
            cnt ++;
            end = ranges[i].r;
        }
    print(res);
    return 0;
}

3. 区间分组

struct Range{
    int l, r;

    bool operator< (const Range& W)const{
        return this->r < W.r;
    }
}ranges[N];

int n;

int main(){
    input();
    sort(ranges, ranges + n);
    priority_queue<int, vector<int>, greater<int> > heap;
    for(int i = 0; i < n; i ++){
        if(heap.empty() || heap.top() >= ranges[i].l)
            heap.push(ranges[i].r);
        else{
            heap.pop();
            heap.push(ranges[i].r);
        }
    }
    print(heap.size());
    return 0;
}

4. 区间覆盖

struct Range{
    int l, r;

    bool operator< (const Range& W)const{
        return this->r < W.r;
    }
}ranges[N];

int n;

int main(){
    input();
    sort(ranges, ranges + n);
    int res = 0;
    bool success = false;
    for(int i = 0; i < n; i ++){
        int j = i, r = -0x3f3f3f3f;
        while(j < n && ranges[j].l <= st){
            r = max(r, ranges[j].r);
            j ++;
        }
        if(r < st){
            success = false;
            break;
        }
        res ++;
        if(r >= ed){
            success = true;
            break;
        }
        st = r;
        i = j - 1;
    }
    if(!success)
        res = -1;
    print(res);
    return 0;
}

Huffman树

int main(){
    int n, res = 0;
    input(n);
    priority_queue<int, vector<int>, greater<int> > heap;
    while(n --){
        int x;
        input(x);
        heap.push(x);
    }
    while(heap.size() > 1){
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        res += a + b;
        heap.push(a + b);
    }
    print(res);
    return 0;
}

排序不等式

1. 排序不等式是什么

已知$a_1 < a_2 < …… < a_n$, $b_1 < b_2 < …… < b_n$, $c_1,c_2,……,c_n$为$b_1,b_2,……,b_n$的一个排列
$顺序和≥乱序和≥逆序和$
<=> $a_1 \times b_1 + a_2 \times b_2 + …… + a_n \times b_n$
$≥ a_1 \times c_1 + a_2 \times c_2 + …… + a_n \times c_n$
$≥ a_1 \times b_n + a_2 \times b_{n-1} + …… + a_n \times b_1$
等号取到当且仅当$a_1 = a_2 = …… = a_n$ 或 $b_1 = b_2 = …… = b_n$

2. 排序不等式的证明

使用调整法

若存在$c_i < c_{i + 1}$ 则交换$c_i与c_{i + 1}$, 可以证明,$交换之后的值会变小$, 即证

3. 排序不等式的应用

int main(){
    input();
    sort(t, t + n);
    long long res = 0;
    for(int i = 0; i < n; i ++)
        res += t[i] * (n - i - 1);
    print(res);
    return 0;
}

绝对值不等式

1. 绝对值不等式是什么

$记f(x) = |a_1 - x| + |a_2 - x| + …… + |a_n - x|$ 且 $a_1 < a_2 < …… < a_n$
当$n为奇数时, x = a_{(n + 1) \div 2}$, $当n为偶数时, a_{n \div 2} ≤ x ≤ a_{n \div 2 + 1}$, $f(x)$取到最小值

2. 绝对值不等式的证明

引理：设$g(x) = |a - x| + |b - x|$
则$g(x)_{Min} ≥ |b - a|$, 等号当且仅当$x \in [a, b]$

引理的证明：采用零点分段法即证

回到原题, 将第$1$个与第$n$个分成一组, 第$2$个与第$n - 1$个分成一组, ……
在每一组里运用引理, 即证绝对值不等式

3. 绝对值不等式的应用

int main(){
    input();
    sort(a, a + n);
    long long res = 0;
    for(int i = 0; i < n; i ++)
        res += abs(a[i] - a[n / 2]);
    print(res);
    return 0;
}

推公式

struct Cow{
    int w, s;

    bool operator< (const Cow& W) const{
        return w + s < W.w + W.s;
    }
}cows[N];

int n;

int main(){
    input();
    sort(cows, cows + n);
    int res = -2e9, sum = 0;
    for(int i = 0; i < n; i ++){
        res = max(res, sum - cows[i].s);
        sum += cows[i].w;
    }
    print(res);
    return 0;
}