贪心/局部交叉型

scandi2025-02-182025-04-01

贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。而局部交叉型贪心是其中的一类体型（名字我自己取的

局部交叉型

贪心题中常常是从顺序角度入手，例如有多个部分，不同的顺序对待这些部分会有不同的效果，而贪心就是得到最符合要求的效果的顺序。
假设一道题有 A - B - C - D - E 五个部分，而最终的贪心顺序假如是 E - D - C - B - A 此时如果发现任意相邻两者的交换，对前面和后面都没有影响，只有对交换的双方有影响，就属于这类题型，我称它为局部交叉型

例题

题目大意：n 个活动，每个活动有需要时长 C 和截止时长 D 两个量，同一时间只能完成一个活动，对于每个活动最后完成时，超出它的截止时长的部分，加入总扣分，问使得总扣分最少的情况是多少？

分析：

1.假设最优策略中 a，b 活动相邻。即。。。ab。。。。
2.发现a和b交换顺序后，对前面和后面的所有任务的完成情况没有影响，只有影响a和b自己--->“局部”
3.设ab前面所花时间为 t
4.交换ab前，a的扣分a1：(t + Ca - Da) b的扣分b1：(t + Ca + Cb - Db)
5.交换ab为ba后，a的扣分a2：(t + Ca + Cb - Da) b的扣分b2：(t + Cb - Db)
6.显然a1 < a2, b1 > b2
7.因为交换前是最优策略，所以必须有a2 > b1 得 Da < Db ------>“交叉”

所以本题的最优策略应该按照需要时间 C 来排顺序！这就简单啦~

ac 代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
//结构体为每个活动，存放用时c和截止时d
struct ty
{
    int c, d;
}a[100005];
//sort比较，按照截止时d升序排序
bool cmp(ty a, ty b)
{
    return a.d < b.d;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].c, &a[i].d);
    sort(a + 1, a + 1 + n, cmp);
    long long sum = 0, ans = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += a[i].c;
        //注意0的类型也得是long long，max函数比较的双方数据类型得一样
        ans += max(0ll, sum - a[i].d);
    }
    cout << ans << endl;
    return 0;
}